解题思路

这题与组合总和(LC39)的区别在于给的candidates中有重复的元素，题目要求每个数字在一个组合中只能使用一次，那么这里有两种方法，第一种就是直接使用哈希表记录元素，第二种则比较简单，使用startIndex，由于candidates在开始已经被排序了，那么只要

i > startIndex 且 nums[i] == nums[i - 1]时可以直接continue避免使用重复元素

代码

Python

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

            for i in range(start, len(candidates)):
                if s + candidates[i] > target: return
                if i > start and candidates[i] == candidates[i -1]: continue
                temp.append(candidates[i])
                backtracking(i + 1, s + candidates[i])
                temp.pop()
        
        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 {
private:
    vector<vector<int>> answer;
    vector<int> temp;
    void backtracking(vector<int>& candidates, int target, int start, int sum) {
        if (sum == target) {
            answer.push_back(temp);
            return;
        }
        for (int i = start; i < candidates.size() && sum + candidates[i] <= target; ++i) {
            if (i > start && candidates[i] == candidates[i - 1]) continue;
            temp.push_back(candidates[i]);
            backtracking(candidates, target, i + 1, sum + candidates[i]);
            temp.pop_back();
        }
    }

public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        backtracking(candidates, target, 0, 0);
        return answer;
    }
};

Go

var (
    answer [][]int
    temp []int
)

func combinationSum2(candidates []int, target int) [][]int {
    answer = [][]int{}
    temp = []int{}
    sort.Ints(candidates)
    backtracking(candidates, target, 0, 0)
    return answer
}

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