解题思路

就是按照题目要求从1开始遍历到9，当发现可以数组内的和达到n时就添加至result,若数组长度超过k则回溯。

代码

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        ans = []
        temp = []
        def backtracking(num, s):
            nonlocal temp
            if len(temp) == k and s == n:
                ans.append(temp.copy())
            elif len(temp) == k: return
            elif s > n: return
            
            for number in range(num, 10):
                temp.append(number)
                s += number
                backtracking(number + 1, s)
                s -= temp.pop()
        backtracking(1, 0)
        return ans

C++

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
class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> ans;
        vector<int> temp;
        backtracking(k, n, 1, 0, ans, temp);
        return ans;
    }

    void backtracking(int k, int n, int num, int s, vector<vector<int>> &ans, vector<int> temp) {
        if (temp.size() == k && s == n) {
            ans.push_back(temp);
            return;
        } else if (temp.size() == k) return;
        
        for (int x = num; x < 10; ++x) {
            if (s + x > n) return;
            temp.push_back(x);
            s += x;
            backtracking(k, n, x + 1, s, ans, temp);
            s -= x;
            temp.pop_back();
        }
    }
};

Go

func combinationSum3(k int, n int) [][]int {
    ans := make([][]int, 0, 0)
    temp := make([]int, 0, 0)
    backtracking(k, n, 1, 0, &ans, temp)
    return ans
}

func backtracking(k int, n int, num int, s int, ans *[][]int, temp []int) {
	if len(temp) == k && s == n {
        t := make([]int, k)
		copy(t, temp)
		*ans = append(*ans, t)
		return
	} else if len(temp) == k {
		return
	}

	for x := num; x < 10; x++ {
		if s+x > n {
			return
		}
		s += x
		temp = append(temp, x)
		backtracking(k, n, x + 1, s, ans, temp)
		temp = temp[:len(temp)-1]
		s -= x
	}
}