LeetCode 40、组合总和II

视频地址：LeetCode 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]
]

示例 2:

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

提示:

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

二、题目解析

三、参考代码

Java

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
class Solution {

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

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {

        List<Integer> path = new ArrayList<>();
    
       // 先排序，方便把相同的元素集中到一起
        Arrays.sort(candidates);

        backtrack( candidates , target , path , 0 );

        return res;
    }

    // 1、画出递归树，找到状态变量(回溯函数的参数)
    // start 表示递归时正在访问的数组元素下标
    // nums 表示当前集合中的元素
    // target 表示想在当前区间拼凑出的目标值
    // path 表示选择的路径
    private void backtrack(int[] nums,int target,List<Integer> path,int start) {
    
        // 2、寻找结束条件，由于回溯算法是借助递归实现，所以也就是去寻找递归终止条件
        if (target < 0) {
            // 一些逻辑操作（可有可无，视情况而定）
            // 比如，在 N 皇后问题中，在这一步把数据加入到了结果里面
            return;
        }

        if(target == 0 ){
            
            // 找到一个组合了
            res.add(new ArrayList(path));

            return;
        }
            
        // 3、确定选择列表，即需要把什么数据存储到结果里面
        // for 循环就是一个选择的过程
        // i 等于 start 表示，后续可以选的元素一开始只能从 start 开始
        // 比如 nums = [2,3,6,7]
        // i = 1，指向了元素 3 ，表示当前后续选择的过程中，只能从 3 开始选，可以重复选 3 ，但无法选 2 了
        // i = 2，指向了元素 6 ，表示当前后续选择的过程中，只能从 6 开始选，可以重复选 6 ，但无法选 2、3 了
        for (int i = start ; i < nums.length ; i++ ) {

            // 剪枝操作：同一层相同数值的结点，从第 2 个开始，结果一定发生重复，因此跳过，用 continue
            if( i > start && nums[i] == nums[i - 1]){
                continue;
            }
            

            // 当前路径上可以把 nums[i] 加上
            path.add(nums[i]);

            // 一些逻辑操作（可有可无，视情况而定）
            // 4、判断是否需要剪枝，去判断此时存储的数据是否之前已经被存储过
            // 需要剪枝
            // 此时，目标值 target，已经从 target 变成了 target - nums[i]
            // 接下来需要去【某个区间中】拼凑 target - nums[i]
            // 由于每个数字在每个组合中只能使用 一次 
            // 当前正在使用 nums[i]，那么为了拼凑 target - nums[i]，需要从使用 nums[i+1] 开始
            // 而 i 前面的元素，比如 num[i]、 num[i-1]无法继续使用，实现了剪枝操作
            int nowposition = i ; 

            // 5、做出选择，递归调用该函数，进入下一层继续搜索
            // 递归
            backtrack(nums, target - nums[i] , path , nowposition + 1 );
        
            // 一些逻辑操作（可有可无，视情况而定）

            // 6、撤销选择，回到上一层的状态
            path.remove(path.size()-1);
        }
    }
}

Python

class Solution:
    def __init__(self):
        self.res = []

    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        path = []

        # 先排序，方便把相同的元素集中到一起
        candidates.sort()

        self.backtrack(candidates, target, path, 0)
        return self.res

    # 1、画出递归树，找到状态变量(回溯函数的参数)
    # start 表示递归时正在访问的数组元素下标
    # nums 表示当前集合中的元素
    # target 表示想在当前区间拼凑出的目标值
    # path 表示选择的路径
    def backtrack(self, nums: List[int], target: int, path: List[int], start: int) -> None:
        # 2、寻找结束条件，由于回溯算法是借助递归实现，所以也就是去寻找递归终止条件
        if target < 0:
            # 一些逻辑操作（可有可无，视情况而定）
            # 比如，在 N 皇后问题中，在这一步把数据加入到了结果里面
            return

        if target == 0:
            # 找到一个组合了
            self.res.append(list(path))
            return

        # 3、确定选择列表，即需要把什么数据存储到结果里面
        # for 循环就是一个选择的过程
        # i 等于 start 表示，后续可以选的元素一开始只能从 start 开始
        # 比如 nums = [2,3,6,7]
        # i = 1，指向了元素 3 ，表示当前后续选择的过程中，只能从 3 开始选，可以重复选 3 ，但无法选 2 了
        # i = 2，指向了元素 6 ，表示当前后续选择的过程中，只能从 6 开始选，可以重复选 6 ，但无法选 2、3 了
        for i in range(start, len(nums)):

            # 剪枝操作：同一层相同数值的结点，从第 2 个开始，结果一定发生重复，因此跳过，用 continue
            if i > start and nums[i] == nums[i - 1]:
                continue

            # 当前路径上可以把 nums[i] 加上
            path.append(nums[i])
            # 一些逻辑操作（可有可无，视情况而定）
            # 4、判断是否需要剪枝，去判断此时存储的数据是否之前已经被存储过
            # 需要剪枝
            # 此时，目标值 target，已经从 target 变成了 target - nums[i]
            # 接下来需要去【某个区间中】拼凑 target - nums[i]
            # 由于 同一个 数字可以 无限制重复被选取
            # 当前正在使用 nums[i]，那么为了拼凑 target - nums[i]，依旧可以继续从使用 nums[i] 开始
            # 而 i 前面的元素，比如 num[i-1]、 num[i-2]无法继续使用，实现了剪枝操作
            now_position = i + 1

            # 5、做出选择，递归调用该函数，进入下一层继续搜索
            # 递归
            self.backtrack(nums, target - nums[i], path, now_position)

            # 一些逻辑操作（可有可无，视情况而定）

            # 6、撤销选择，回到上一层的状态
            path.pop()

C++

class Solution {
public:
    vector<vector<int>> res;

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<int> path;
        // 先排序，方便把相同的元素集中到一起
        sort(candidates.begin(), candidates.end());
        backtrack(candidates, target, path, 0);
        return res;
    }

private:
    void backtrack(vector<int>& nums, int target, vector<int>& path, int start) {
        // 寻找结束条件
        if (target < 0) return;
        if (target == 0) {
            res.push_back(path);
            return;
        }

        for (int i = start; i < nums.size(); i++) {
            // 剪枝操作：同一层相同数值的节点跳过
            if (i > start && nums[i] == nums[i - 1]) continue;

            // 当前路径上加入 nums[i]
            path.push_back(nums[i]);

            // 递归，进入下一层
            backtrack(nums, target - nums[i], path, i + 1);

            // 撤销选择，回到上一层状态
            path.pop_back();
        }
    }
};

C

void backtrack(int* nums, int numsSize, int target, int* path, int pathSize, int start, int** result, int* returnSize, int* returnColumnSizes) {
    // 如果目标值小于0，直接返回
    if (target < 0) return;

    // 如果目标值为0，找到一个组合
    if (target == 0) {
        result[*returnSize] = (int*)malloc(pathSize * sizeof(int));
        for (int i = 0; i < pathSize; i++) {
            result[*returnSize][i] = path[i];
        }
        returnColumnSizes[*returnSize] = pathSize;
        (*returnSize)++;
        return;
    }

    for (int i = start; i < numsSize; i++) {
        // 剪枝操作：同一层相同数值的节点跳过
        if (i > start && nums[i] == nums[i - 1]) continue;

        path[pathSize] = nums[i];
        backtrack(nums, numsSize, target - nums[i], path, pathSize + 1, i + 1, result, returnSize, returnColumnSizes);
    }
}

int** combinationSum2(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes) {
    int** result = (int**)malloc(1000 * sizeof(int*));
    int* path = (int*)malloc(1000 * sizeof(int));
    *returnSize = 0;
    *returnColumnSizes = (int*)malloc(1000 * sizeof(int));

    // 排序以便剪枝
    qsort(candidates, candidatesSize, sizeof(int), (int (*)(const void*, const void*))strcmp);

    backtrack(candidates, candidatesSize, target, path, 0, 0, result, returnSize, *returnColumnSizes);
    free(path);
    return result;
}

Node JavaScript

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function(candidates, target) {
    const res = [];
    const path = [];

    // 排序方便剪枝
    candidates.sort((a, b) => a - b);

    const backtrack = (nums, target, path, start) => {
        if (target < 0) return;
        if (target === 0) {
            res.push([...path]);
            return;
        }

        for (let i = start; i < nums.length; i++) {
            // 剪枝操作：同一层相同数值的节点跳过
            if (i > start && nums[i] === nums[i - 1]) continue;

            path.push(nums[i]);
            backtrack(nums, target - nums[i], path, i + 1);
            path.pop();
        }
    };

    backtrack(candidates, target, path, 0);
    return res;
};

Go

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

    // 排序方便剪枝
    sort.Ints(candidates)

    var backtrack func(nums []int, target int, start int)
    backtrack = func(nums []int, target int, start int) {
        if target < 0 {
            return
        }
        if target == 0 {
            temp := make([]int, len(path))
            copy(temp, path)
            res = append(res, temp)
            return
        }

        for i := start; i < len(nums); i++ {
            // 剪枝操作：同一层相同数值的节点跳过
            if i > start && nums[i] == nums[i-1] {
                continue
            }

            path = append(path, nums[i])
            backtrack(nums, target-nums[i], i+1)
            path = path[:len(path)-1]
        }
    }

    backtrack(candidates, target, 0)
    return res
}