Combination Sum III Problem


Description

LeetCode Problem 216.

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:

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

Example 2:

1
2
3
4
5
6
7
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:

1
2
3
4
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.

Example 4:

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

Example 5:

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

Constraints:

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


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    vector<vector<int>> ans;
    int steps;
    
    void dfs(vector<int>& candidates, vector<int>&comb, 
             int target, int cnt, int idx) {
        if (cnt == steps && target == 0) {
            ans.push_back(comb);
            return;
        }
        if (cnt >= steps || target <= 0)
            return;
        
        for (int i = idx; i < candidates.size(); i ++) {
            if (target >= candidates[i]) {
                comb.push_back(candidates[i]);
                dfs(candidates, comb, target-candidates[i], cnt+1, i+1);
                comb.pop_back();
            }
        }
    }
    
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<int> candidates = {1,2,3,4,5,6,7,8,9};
        steps = k;
        vector<int> comb;
        dfs(candidates, comb, n, 0, 0);
        return ans;
    }
};




Related Posts

Combination Sum III Problem

LeetCode 216. Find all valid combinations of k numbers that...

Palindrome Partitioning Problem

LeetCode 131. Given a string s, partition s such that...

Word Search Problem

LeetCode 79. Given an m x n grid of characters...

Subsets Problem

LeetCode 78. Given an integer array nums of unique elements,...

Subsets II Problem

LeetCode 90. Given an integer array nums that may contain...

Restore IP Addresses Problem

LeetCode 93. Given a string s containing only digits, return...