解题思路

这题就是排序直接使用回溯，考点可能就是几个剪枝的地方。

  1. 当总和 > target时

代码

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        answer = []
        def backtracking(start: int, temp: list[int], s: int):
            if s == target:
                answer.append(temp.copy())
                return

            for i in range(start, len(candidates)):
                if s + candidates[i] > target: return
                temp.append(candidates[i])
                backtracking(i, temp, s + candidates[i])
                temp.pop()
        
        candidates.sort()
        backtracking(0, [], 0)
        return answer

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
class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> answer;
        vector<int> temp;
        sort(candidates.begin(), candidates.end());
        backtracking(candidates, target, 0, 0, temp, answer);
        return answer;
    }

    void backtracking(vector<int> &candidates, int target, int start, int sum, vector<int> temp, vector<vector<int>> &answer) {
        if (sum == target) {
            answer.push_back(temp);
            return;
        }
        
        for (int i = start; i < candidates.size(); ++i) {
            if (sum + candidates[i] > target) return;
            temp.push_back(candidates[i]);
            backtracking(candidates, target, i, sum + candidates[i], temp, answer);
            temp.pop_back();
        }
    }
};

Go

func combinationSum(candidates []int, target int) [][]int {
    answer := make([][]int, 0, 0)
    sort.Ints(candidates)
    backtracking(candidates, target, 0, make([]int, 0, 0), 0, &answer)
    return answer
}

func backtracking(candidates []int, target int, start int, temp []int, sum int, answer *[][]int) {
    if sum == target {
        t := make([]int, len(temp))
        copy(t, temp)
        *answer = append(*answer, t)
        return
    }

    for i := start; i < len(candidates); i++ {
        if sum + candidates[i] > target {return}
        temp = append(temp, candidates[i])
        backtracking(candidates, target, i, temp, sum + candidates[i], answer)
        temp = temp[:len(temp) - 1]
    }
}