☆打卡算法☆LeetCode 40、组合总和 II 算法解析

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定一个数组和目标数，找出数组中所有可以使数组和为目标数的组合。”

40题跟39题的区别在于，40题不能包含重复的组合。

题目链接：

来源：力扣（LeetCode）

链接：40. 组合总和 II - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

给定一个数组 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、思路分析

这个题需要求出所有和为目标数的组合，并且每个数只能使用一次，可以使用递归＋回溯的方法解决这个味问题。

首先，因为题目不能出现重复的组合，所以需要先将相同的数放在一起处理，也就是说，在递归的时候一起处理，这样就不会得到重复的组合。

使用哈希映射统计数组中每个数出现的次数，统计完放到一个列表中，在递归的时候调用。

2、代码实现

代码参考：

public class Solution {
    public IList<IList<int>> CombinationSum2(int[] candidates, int target) {
        Array.Sort(candidates);
        IList<IList<int>> lstAllRes = new List<IList<int>>();
        Stack<int> path = new Stack<int>();
        dfs(candidates, target, candidates.Length, 0, path, lstAllRes);
        return lstAllRes;
    }

    private void dfs(int[] nums, int target, int n, int begin, Stack<int> path, IList<IList<int>> lstAllRes){
        if(SumOfStack(path) == target){
            lstAllRes.Add(new List<int>(path));
            return;
        }else if(SumOfStack(path) > target){
            return;
        }

        for(int i = begin; i < n; i++){
            if(i > begin && nums[i] == nums[i - 1]){
                continue;
            }
            path.Push(nums[i]);
            dfs(nums, target, n, i + 1, path, lstAllRes);
            path.Pop();
        }
    }

    private int SumOfStack(Stack<int> stack){
        int res = 0;
        foreach(int num in stack){
            res += num;
        }
        return res;
    }
}

3、时间复杂度

时间复杂度 ： O(n logn)

其中n是数组的长度。

空间复杂度： O(n)

需要O(n)的空间存储列表、递归张工存储当前选择的数的列表，以及递归需要的栈。

三、总结

这道题与39题的不同点就是去重，这也是这道题的难点。

39题可以使用回溯+递归的算法解题，但是并不适用本题，所以还需要改进回溯+递归算法，去除重复的组合。

去重可以使用哈希表，哈希表具有天然的去重功能，但是编码相对复杂，所以可以将不重复的按顺序搜索，在搜索的过程中检测分钟你是否会出现重复结果。