40. 组合总和 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]
]
1
2
3
4
5
6
7
8
9
10

样例 2：

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

输出:
[
[1,2,2],
[5]
]
1
2
3
4
5
6
7
8

提示：

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

分析：

• 面对这道算法题目，二当家的陷入了沉思。
• 遍历或者递归，递归比较直观，深度优先，回溯。
• 题目要求所有可能的组合，不能重复，本来是需要想办法去重的，但是我们可以曲线救国，我们可以计数去重，还可以排序，排序可以助力剪枝，当处理的数字已经大于目标和时，后面的数字就可以跳过了。
• 计数排序，去重，计数，排序，一下子都搞定。

题解：

rust

impl Solution {
    pub fn combination_sum2(candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
        fn dfs(nums: &Vec<i32>, target: i32, num: i32, row: &mut Vec<i32>, ans: &mut Vec<Vec<i32>>) {
            if target == 0 {
                // 符合条件的一个组合
                ans.push(row.clone());
                return;
            }
            if num as usize == nums.len() || target < num {
                // 尝试到底，开始回溯
                return;
            }
            let count = nums[num as usize].min(target / num);
            (1..count + 1).for_each(|i| {
                // 选择当前下标数字
                row.push(num);
                dfs(nums, target - num * i, num + 1, row, ans);
            });
            row.resize(row.len() - count as usize, 0);
            // 跳过当前下标数字
            dfs(nums, target, num + 1, row, ans);
        }

        // 1 <= candidates[i] <= 50
        let mut nums = vec![0; 51];
        candidates.iter().for_each(|&c| {
            nums[c as usize] += 1;
        });

        let mut ans = Vec::new();

        // 递归深度优先回溯套娃大法
        dfs(&nums, target, 1, &mut Vec::new(), &mut ans);

        return ans;
    }
}
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

go

func combinationSum2(candidates []int, target int) [][]int {
    var ans [][]int

// 1 <= candidates[i] <= 50
nums := make([]int, 51)
for _, c := range candidates {
nums[c]++
}

var dfs func(int, int, []int)
dfs = func(target int, num int, row []int) {
if target == 0 {
// 符合条件的一个组合
ans = append(ans, append([]int{}, row...))
return
}
if num == len(nums) || target < num {
// 尝试到底，开始回溯
return
}
count := target / num
if nums[num] < count {
count = nums[num]
}
// 选择当前下标数字
for i := 1; i <= count; i++ {
row = append(row, num)
dfs(target-num*i, num+1, row)
}
row = row[:len(row)-count]
// 跳过当前下标数字
dfs(target, num+1, row)
}

dfs(target, 1, []int{})

return ans
}
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

c++

class Solution {
private:
    void dfs(vector<int>& nums, int target, int num, vector<int>& row, vector<vector<int>>& ans) {
        if (target == 0) {
            // 符合条件的一个组合
            ans.emplace_back(row);
            return;
        }
        if (num == nums.size() || target < num) {
            // 尝试到底，开始回溯
            return;
        }
        int count = min(target / num, nums[num]);
        for (int i = 1; i <= count; ++i) {
            // 选择当前下标数字
            row.emplace_back(num);
            dfs(nums, target - num * i, num + 1, row, ans);
        }
        for (int i = 1; i <= count; ++i) {
            row.pop_back();
        }
        // 跳过当前下标数字
        dfs(nums, target, num + 1, row, ans);
    }
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> ans;
        vector<int> row;

        vector<int> nums(51);
        for (int c: candidates) {
            ++nums[c];
        }

        dfs(nums, target, 1, row, ans);

        return ans;
    }
};
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

c

void dfs(int *nums, int numsSize, int target, int num, int *row, int rowSize, int **ans, int *returnSize,
         int **returnColumnSizes) {
    if (target == 0) {
        // 符合条件的一个组合
        ans[*returnSize] = (int *) malloc(sizeof(int) * rowSize);
        memcpy(ans[*returnSize], row, sizeof(int) * rowSize);
        (*returnColumnSizes)[*returnSize] = rowSize;
        ++(*returnSize);
        return;
    }
    if (num == numsSize || target < num) {
        // 尝试到底，开始回溯
        return;
    }

    int count = fmin(target / num, nums[num]);
    for (int i = 1; i <= count; ++i) {
        // 选择当前下标数字
        row[rowSize + i - 1] = num;
        dfs(nums, numsSize, target - num * i, num + 1, row, rowSize + i, ans, returnSize, returnColumnSizes);
    }
    // 跳过当前下标数字
    dfs(nums, numsSize, target, num + 1, row, rowSize, ans, returnSize, returnColumnSizes);
}

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int **combinationSum2(int *candidates, int candidatesSize, int target, int *returnSize, int **returnColumnSizes) {
    *returnSize = 0;
    *returnColumnSizes = (int *) malloc(sizeof(int) * 150);
    int **ans = (int **) malloc(sizeof(int *) * 150);
    int row[target];
    int nums[51];
    memset(nums, 0, sizeof(nums));
    for (int i = 0; i < candidatesSize; ++i) {
        ++nums[candidates[i]];
    }

    dfs(nums, 51, target, 1, row, 0, ans, returnSize, returnColumnSizes);

    return ans;
}
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
41
42
43
44
45

python

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        ans = []
        nums = [0] * 51
        for c in candidates:
            nums[c] += 1

        def dfs(target: int, num: int, row: List[int]):
            if target == 0:
                # 符合条件的一个组合
                ans.append(row.copy())
                return
            if num == len(nums) or target < num:
                # 尝试到底，开始回溯
                return
            count = min(target // num, nums[num])
            for i in range(1, count + 1):
                row.append(num)
                dfs(target - num * i, num + 1, row)
            for i in range(1, count + 1):
                row.pop()
            # 跳过当前下标数字
            dfs(target, num + 1, row)

        dfs(target, 1, [])

        return ans

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

java

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        // 1 <= candidates[i] <= 50
        int[] nums = new int[51];
        for (int c : candidates) {
            ++nums[c];
        }

        List<List<Integer>> ans = new ArrayList<>();

        // 递归深度优先回溯套娃大法
        this.dfs(nums, target, 1, new LinkedList<>(), ans);

        return ans;
    }

    private void dfs(int[] nums, int target, int num, Deque<Integer> row, List<List<Integer>> ans) {
        if (target == 0) {
            // 符合条件的一个组合
            ans.add(new ArrayList<>(row));
            return;
        }
        if (num == nums.length || target < num) {
            // 尝试到底，开始回溯
            return;
        }
        int count = Math.min(target / num, nums[num]);
        for (int i = 1; i <= count; ++i) {
            // 选择当前下标数字
            row.addLast(num);
            this.dfs(nums, target - num * i, num + 1, row, ans);
        }
        for (int i = 1; i <= count; ++i) {
            row.pollLast();
        }
        // 跳过当前下标数字
        this.dfs(nums, target, num + 1, row, ans);
    }
}
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

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~