216. Combination Sum III

Description

Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

Only numbers 1 through 9 are used.
Each number is used at most once.

Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

Example 1:

Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation:
1 + 2 + 4 = 7
There are no other valid combinations.

Example 2:

Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.

Example 3:

Input: k = 4, n = 1
Output: []
Explanation: There are no valid combinations.
Using 4 different numbers in the range [1,9], the smallest sum we can get is 1+2+3+4 = 10 and since 10 > 1, there are no valid combination.

Constraints:

2 <= k <= 9
1 <= n <= 60

Solutions

DFS.

This is a typical backtracking problem that explores all possible combinations to find those that meet the criteria.

Function Signature

def combinationSum3(self, k: int, n: int) -> List[List[int]]:

The function combinationSum3 takes two arguments: k, the number of digits in each combination, and n, the target sum.
It returns a list of lists, where each inner list is a combination of k digits that add up to n.

The `dfs` (Depth-First Search) Helper Function

def dfs(start, s, t): # s: sum, t: list

dfs is a recursive helper function defined within combinationSum3. It is used to perform a depth-first search to explore all possible combinations.
start: The starting point for the current exploration, ensuring that only numbers greater than start are considered to avoid repeats and maintain uniqueness.
s: The current sum of the numbers in the temporary list t.
t: A temporary list that stores the current combination being explored.

The Recursive Exploration

The recursion starts with dfs(1, 0, []), meaning the search begins with the number 1, the current sum as 0, and an empty list for the combination.
The base case of the recursion checks if the current sum s exceeds n or if the length of the temporary list t exceeds k. If either condition is true, the recursion returns, as the current path cannot yield a valid combination.
Another base case checks if s == n and len(t) == k. If both conditions are met, a valid combination is found, and a copy of t is added to the answer list ans. The copy is used because t is modified in subsequent steps.
The recursive step iterates from start to 9 (inclusive of 1 and exclusive of 10 because we’re dealing with digits). For each number i in this range, it is added to t, and dfs is called recursively with the updated parameters: the next starting number (i + 1), the new sum (s + i), and the updated temporary list t. After the recursive call returns, t.pop() is called to backtrack, removing the last number added to t and exploring other possibilities.

Collecting and Returning the Answer

ans is initialized as an empty list. It collects all valid combinations found during the depth-first search.
After exploring all possibilities through recursive backtracking, ans is returned, containing all combinations of k numbers that sum to n.

class Solution {
    private List<List<Integer>> ans = new ArrayList<>();
    private List<Integer> t = new ArrayList<>();
    private int k;

    public List<List<Integer>> combinationSum3(int k, int n) {
        this.k = k;
        dfs(1, n);
        return ans;
    }

    private void dfs(int i, int s) {
        if (s == 0) {
            if (t.size() == k) {
                ans.add(new ArrayList<>(t));
            }
            return;
        }
        if (i > 9 || i > s || t.size() >= k) {
            return;
        }
        t.add(i);
        dfs(i + 1, s - i);
        t.remove(t.size() - 1);
        dfs(i + 1, s);
    }
}

class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> ans;
        vector<int> t;
        function<void(int, int)> dfs = [&](int i, int s) {
            if (s == 0) {
                if (t.size() == k) {
                    ans.emplace_back(t);
                }
                return;
            }
            if (i > 9 || i > s || t.size() >= k) {
                return;
            }
            t.emplace_back(i);
            dfs(i + 1, s - i);
            t.pop_back();
            dfs(i + 1, s);
        };
        dfs(1, n);
        return ans;
    }
};

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        def dfs(start, s, t): # s: sum, t: list
            if s > n or len(t) > k:
                return
            if s == n and len(t) == k:
                ans.append(t.copy())
                return

            for i in range(start, 10):
                t.append(i)
                dfs(i + 1, s + i, t)
                t.pop()

        ans = []
        dfs(1, 0, [])
        return ans

func combinationSum3(k int, n int) (ans [][]int) {
	t := []int{}
	var dfs func(i, s int)
	dfs = func(i, s int) {
		if s == 0 {
			if len(t) == k {
				ans = append(ans, slices.Clone(t))
			}
			return
		}
		if i > 9 || i > s || len(t) >= k {
			return
		}
		t = append(t, i)
		dfs(i+1, s-i)
		t = t[:len(t)-1]
		dfs(i+1, s)
	}
	dfs(1, n)
	return
}

function combinationSum3(k: number, n: number): number[][] {
    const ans: number[][] = [];
    const t: number[] = [];
    const dfs = (i: number, s: number) => {
        if (s === 0) {
            if (t.length === k) {
                ans.push(t.slice());
            }
            return;
        }
        if (i > 9 || i > s || t.length > k) {
            return;
        }
        t.push(i);
        dfs(i + 1, s - i);
        t.pop();
        dfs(i + 1, s);
    };
    dfs(1, n);
    return ans;
}

public class Solution {
    private List<IList<int>> ans = new List<IList<int>>();
    private List<int> t = new List<int>();
    private int k;

    public IList<IList<int>> CombinationSum3(int k, int n) {
        this.k = k;
        dfs(1, n);
        return ans;
    }

    private void dfs(int i, int s) {
        if (s == 0) {
            if (t.Count == k) {
                ans.Add(new List<int>(t));
            }
            return;
        }
        if (i > 9 || i > s || t.Count >= k) {
            return;
        }
        t.Add(i);
        dfs(i + 1, s - i);
        t.RemoveAt(t.Count - 1);
        dfs(i + 1, s);
    }
}

impl Solution {
    #[allow(dead_code)]
    pub fn combination_sum3(k: i32, n: i32) -> Vec<Vec<i32>> {
        let mut ret = Vec::new();
        let mut candidates = (1..=9).collect();
        let mut cur_vec = Vec::new();
        Self::dfs(n, k, 0, 0, &mut cur_vec, &mut candidates, &mut ret);
        ret
    }

    #[allow(dead_code)]
    fn dfs(
        target: i32,
        length: i32,
        cur_index: usize,
        cur_sum: i32,
        cur_vec: &mut Vec<i32>,
        candidates: &Vec<i32>,
        ans: &mut Vec<Vec<i32>>
    ) {
        if cur_sum > target || cur_vec.len() > (length as usize) {
            // No answer for this
            return;
        }
        if cur_sum == target && cur_vec.len() == (length as usize) {
            // We get an answer
            ans.push(cur_vec.clone());
            return;
        }
        for i in cur_index..candidates.len() {
            cur_vec.push(candidates[i]);
            Self::dfs(target, length, i + 1, cur_sum + candidates[i], cur_vec, candidates, ans);
            cur_vec.pop().unwrap();
        }
    }
}

216 - Combination Sum III

216. Combination Sum III

Description

Solutions

Function Signature

The `dfs` (Depth-First Search) Helper Function

The Recursive Exploration

Collecting and Returning the Answer

All Problems

All Solutions

Welcome to Subscribe On Youtube

216. Combination Sum III

Description

Solutions

Function Signature

The dfs (Depth-First Search) Helper Function

The Recursive Exploration

Collecting and Returning the Answer

All Problems

All Solutions

The `dfs` (Depth-First Search) Helper Function