Question

Formatted question description: https://leetcode.ca/all/216.html

 216. Combination Sum III

 Find all possible combinations of k numbers that add up to a number n,
 given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

 Note:
     All numbers will be positive integers.
     The solution set must not contain duplicate combinations.

 Example 1:

 Input: k = 3, n = 7
 Output: [[1,2,4]]

 Example 2:

 Input: k = 3, n = 9
 Output: [[1,2,6], [1,3,5], [2,3,4]]

Algorithm

Regular DFS.

n is the sum of k numbers.

  • If n is less than 0, return directly.
  • If n is exactly equal to 0, and the number of digits in out at this time is exactly k, it means that it is a correct solution at this time.

Code

Java

  • import java.util.ArrayList;
    import java.util.List;
    
    
    public class Combination_Sum_III {
        class Solution {
    
            List<List<Integer>> result = new ArrayList<List<Integer>>();
    
            public List<List<Integer>> combinationSum3(int k, int n) {
                List<Integer> curr = new ArrayList<Integer>();
    
                dfs(curr, k, 1, n);
    
                return result;
            }
    
            private void dfs(List<Integer> curr, int k, int start, int sum) {
                if (sum < 0) {
                    return;
                }
    
                if (sum == 0 && curr.size() == k) {
                    result.add(new ArrayList<Integer>(curr));
                    return;
                }
    
                for (int i = start; i <= 9; i++) {
                    curr.add(i);
                    dfs(curr, k, i + 1, sum - i);
                    curr.remove(curr.size() - 1);
                }
            }
        }
    }
    
  • // OJ: https://leetcode.com/problems/combination-sum-iii/
    // Time: O(2^9 * 9)
    // Space: O(9)
    class Solution {
        vector<vector<int>> ans;
        vector<int> tmp;
        void dfs(int k, int n, int start) {
            if (!k || !n) {
                if (!k && !n) ans.push_back(tmp);
                return;
            }
            for (int i = start; i <= min(9, n); ++i) {
                tmp.push_back(i);
                dfs(k - 1, n - i, i + 1);
                tmp.pop_back();
            }
        }
    public:
        vector<vector<int>> combinationSum3(int k, int n) {
            dfs(k, n, 1);
            return ans;
        }
    };
    
  • class Solution(object):
      def combinationSum3(self, k, n):
        """
        :type k: int
        :type n: int
        :rtype: List[List[int]]
        """
    
        def dfs(k, start, path, subsum, res, visited):
          if len(path) == k and subsum == 0:
            res.append(path + [])
            return
          if len(path) >= k or subsum <= 0:
            return
    
          for i in range(start, 10):
            if visited[i] == 0:
              visited[i] = 1
              path.append(i)
              dfs(k, i + 1, path, subsum - i, res, visited)
              visited[i] = 0
              path.pop()
    
        visited = [0] * 10
        res = []
        dfs(k, 1, [], n, res, visited)
        return res
    
    

All Problems

All Solutions