Welcome to Subscribe On Youtube

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();
            }
        }
    }
    
    
  • function combinationSum3(k, n) {
        const ans = [];
        const t = [];
        const dfs = (i, s) => {
            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;
    }
    
    

All Problems

All Solutions