216. Combination Sum III

  • 43.2%

https://leetcode.com/problems/combination-sum-iii/description/

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.

1
2
3
4
5
6
7
Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]
1
2
3
4
5
6
7
Example 2:

Input: k = 3, n = 9

Output:

[[1,2,6], [1,3,5], [2,3,4]]

方法一:

回溯法,我的代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> res;
vector<int> combination;
helper(k, n, 1, combination, res);
return res;
}

void helper(int k, int target, int start, vector<int>& combination, vector<vector<int>>& res){
if(target==0 && k==0){
res.push_back(combination);
return;
}
if(k<=0 || target<0)
return;
for(int i=start; i<10; i++){
combination.push_back(i);
helper(k-1, target-i, i+1, combination, res);
combination.pop_back();
}
}
};

Use backtrack c++ solution, easy to understand.

下段代码值得借鉴的是backtrack的判断条件

i<=10-k && i<=target

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> result;
vector<int> path;
backtrack(result, path, 1, k, n);
return result;
}

void backtrack(vector<vector<int>> &result, vector<int> &path, int start, int k, int target){
if(target==0&&k==0){
result.push_back(path);
return;
}
for(int i=start;i<=10-k&&i<=target;i++){
path.push_back(i);
backtrack(result,path,i+1,k-1,target-i);
path.pop_back();
}
}

https://discuss.leetcode.com/topic/14641/my-c-solution-backtracking

My C++ solution, backtracking.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
void combination(vector<vector<int>>& result, vector<int> sol, int k, int n) {
if (sol.size() == k && n == 0) { result.push_back(sol); return ; }
if (sol.size() < k) {
for (int i = sol.empty() ? 1 : sol.back() + 1; i <= 9; ++i) {
if (n - i < 0) break;
sol.push_back(i);
combination(result, sol, k, n - i);
sol.pop_back();
}
}
}

vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> result;
vector<int> sol;
combination(result, sol, k, n);
return result;
}
};

https://discuss.leetcode.com/topic/25351/use-backtrack-c-solution-easy-to-understand

Use backtrack c++ solution, easy to understand.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> result;
vector<int> path;
backtrack(result, path, 1, k, n);
return result;
}

void backtrack(vector<vector<int>> &result, vector<int> &path, int start, int k, int target){
if(target==0&&k==0){
result.push_back(path);
return;
}
for(int i=start;i<=10-k&&i<=target;i++){
path.push_back(i);
backtrack(result,path,i+1,k-1,target-i);
path.pop_back();
}
}

52ms, 43.32%, June.18th, 2016

https://leetcode.com/discuss/38132/concise-python-solution-using-dfs

Concise python solution using DFS

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
class Solution:
# @param {integer} k
# @param {integer} n
# @return {integer[][]}
def combinationSum3(self, k, n):
if n > sum([i for i in range(1, 11)]):
return []

res = []
self.sum_help(k, n, 1, [], res)
return res


def sum_help(self, k, n, curr, arr, res):
if len(arr) == k:
if sum(arr) == n:
res.append(list(arr))
return

if len(arr) > k or curr > 9:
return

for i in range(curr, 10):
arr.append(i)
self.sum_help(k, n, i + 1, arr, res)
arr.pop()

https://discuss.leetcode.com/topic/14702/clean-1-6-7-liners-ac

Clean 1/6/7-liners (AC)

Batteries Included

AC in 44ms

First the obligatory “use the darn library” solution. Create all k-combinations of digits and keep those with sum n:

1
2
3
4
5
from itertools import combinations

class Solution:
def combinationSum3(self, k, n):
return [c for c in combinations(range(1, 10), k) if sum(c) == n]

Recursive

AC in 48 ms

But it’s more interesting to do it on your own. Here I use a recursive helper function getting the same k and n as the main function, and an additional cap under which all the numbers have to be:

1
2
3
4
5
6
7
8
9
class Solution:
def combinationSum3(self, k, n):
def combs(k, n, cap):
if not k:
return [[]] * (not n)
return [comb + [last]
for last in range(1, cap)
for comb in combs(k-1, n-last, last)]
return combs(k, n, 10)

Iterative

AC in 56 ms

And an iterative version doing pretty much the same thing, except this time I prepend elements on the left, and use the first element of a partial combination as the cap.

1
2
3
4
5
6
7
8
class Solution:
def combinationSum3(self, k, n):
combs = [[]]
for _ in range(k):
combs = [[first] + comb
for comb in combs
for first in range(1, comb[0] if comb else 10)]
return [c for c in combs if sum(c) == n]

Reduce

AC in 44 ms

And here’s a “one-liner” version of the iterative solution using reduce instead of the loop:

1
2
3
4
5
6
7
8
class Solution:
def combinationSum3(self, k, n):
return [c for c in
reduce(lambda combs, _: [[first] + comb
for comb in combs
for first in range(1, comb[0] if comb else 10)],
range(k), [[]])
if sum(c) == n]

I note that all these solutions also correctly solve the cases with k=0 and/or n=0 (but leetcode sadly doesn’t test those).


https://discuss.leetcode.com/topic/19100/easy-to-understand-python-solution-backtracking

Easy to understand Python solution (backtracking).

1
2
3
4
5
6
7
8
9
10
11
12
def combinationSum3(self, k, n):
res = []
self.dfs(xrange(1,10), k, n, 0, [], res)
return res

def dfs(self, nums, k, n, index, path, res):
if k < 0 or n < 0: # backtracking
return
if k == 0 and n == 0:
res.append(path)
for i in xrange(index, len(nums)):
self.dfs(nums, k-1, n-nums[i], i+1, path+[nums[i]], res)
谢谢你,可爱的朋友。