40.组合总和 II：回溯 + 剪枝

【LetMeFly】40.组合总和 II：回溯 + 剪枝

力扣题目链接：https://leetcode.cn/problems/combination-sum-ii/

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。 

 

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

 

提示:

  • 1 <= candidates.length <= 100
  • 1 <= candidates[i] <= 50
  • 1 <= target <= 30

解题方法：回溯（剪枝）

类似39.组合总和：回溯 + 剪枝，但这道题比较困难的地方在于，candidates中有重复的元素，而答案中不能有重复的数组。

怎么办呢，排序呗。刚开始还和之前一样走正常流程：

  1. 如果target已经达到则将当前方案加入答案数组。
  2. 如果已超target则直接返回
  3. 选当前元素并回溯
  4. 不选当前元素

不同之处在于，不选当前元素时，要保证选择的下一个元素和当前元素不同。

例如[4, 4, 5]，不选第一个4的话，就不能选第二个4。

否则的话，可能会出现第一个4和5、第二个4和5这两种相同的方案。

  • 时间复杂度$O(len(candidates)^2)$
  • 空间复杂度$O(len(candidates))$

AC代码

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
26
27
28
29
30
31
32
33
34
35
36
37
/*
 * @Author: LetMeFly
 * @Date: 2025-01-26 07:27:24
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-01-26 07:57:37
 */
class Solution {
private:
    vector<vector<int>> ans;
    vector<int> now;

    void dfs(vector<int>& c, int target, int index) {
        // 组合成功
        if (!target) {
            ans.push_back(now);
            return;
        }
        // 不再可能
        if (index == c.size() || target < 0) {
            return;
        }
        // 选当前
        now.push_back(c[index]);
        dfs(c, target - c[index], index + 1);
        now.pop_back();
        // 不选当前递归下一个
        int next = index;
        while (++next < c.size() && c[next] == c[index]);
        dfs(c, target, next);
    }
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        dfs(candidates, target, 0);
        return ans;
    }
};

Python

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
'''
Author: LetMeFly
Date: 2025-01-26 07:58:11
LastEditors: LetMeFly.xyz
LastEditTime: 2025-01-26 08:01:59
'''
from typing import List

class Solution:
    def dfs(self, target: int, index: int) -> None:
        if not target:
            self.ans.append([i for i in self.now])
            return
        if index == len(self.c) or target < 0:
            return
        self.now.append(self.c[index])
        self.dfs(target - self.c[index], index + 1)
        self.now.pop()
        next = index + 1
        while next < len(self.c) and self.c[next] == self.c[index]:
            next += 1
        self.dfs(target, next)
    
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        self.c = candidates
        self.ans = []
        self.now = []
        self.dfs(target, 0)
        return self.ans

Java

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
32
33
34
35
36
37
38
39
40
/*
 * @Author: LetMeFly
 * @Date: 2025-01-26 08:02:41
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-01-26 08:10:08
 */
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;

class Solution {
    private List<List<Integer>> ans;
    private List<Integer> now;
    private int[] c;

    private void dfs(int target, int index) {
        if (target == 0) {
            ans.add(new ArrayList<>(now));
            return;
        }
        if (index == c.length || target < 0) {
            return;
        }
        now.add(c[index]);
        dfs(target - c[index], index + 1);
        now.remove(now.size() - 1);
        int next = index;
        while (++next < c.length && c[next] == c[index]);
        dfs(target, next);
    }

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        c = candidates;
        ans = new ArrayList<>();
        now = new ArrayList<>();
        dfs(target, 0);
        return ans;
    }
}

Go

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
32
33
34
35
/*
 * @Author: LetMeFly
 * @Date: 2025-01-26 08:47:10
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-01-26 09:01:49
 * @Descreption: AC,100.00%,34.12%
 */
package main

import "sort"

func dfs(c []int, target int, now []int, index int, ans *[][]int) {
    if target == 0 {
        *ans = append(*ans, append([]int{}, now...))
        return
    }
    if index == len(c) || target < 0 {
        return
    }
    now = append(now, c[index])
    dfs(c, target - c[index], now, index + 1, ans)
    now = now[:len(now) - 1]
    next := index + 1
    for next < len(c) && c[next] == c[index] {
        next++
    }
    dfs(c, target, now, next, ans)
}

func combinationSum2(candidates []int, target int) (ans [][]int) {
    var now []int
    sort.Ints(candidates)
    dfs(candidates, target, now, 0, &ans)
    return
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/145363298