组合总和--回溯法

LeetCode

组合总和Ⅱ

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

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

说明：

• 所有数字（包括目标数）都是正整数。
• 解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
    [1, 7],
    [1, 2, 5],
    [2, 6],
    [1, 1, 6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
    [1,2,2],
    [5]
]

解法：回溯法

解题思路：回溯法的基本思想就是，从最优解出发，当不能得到最优解时，往前退一步

举个例子：求列表[1,2,2,2,5]中的数字组合为5的组合，并且每个数字在每个组合中只能被使用一次

• 首先，我们会选择1
• 选择1之后，我们再选择2，这时候列表中可用数字只有[2,2,5]了
• 这时候我们再选择2，发现刚好组合出5，这时候，这个组合就是我们要的
• 现在回到选择1之后的那一步，我们要再尝试其他组合，所以选了第三个位置的2([1,2,2,2,5]),我们可以发现，这个2跟我们上次选的是一样的，而上次的列表为[2,2,5],这次的列表为[2,5],所以上次的组合肯定包含了这一次的，所以我们对其进行剪枝
• 同理，选择1之后再选了第四个位置的2([1,2,2,2,5]),剪枝
• 最后，选择1之后选择了5，发现结果为6>5,所以这时候我们要回溯了
• 回溯到选择1之前，我们选择第二个位置的2([1,2,2,2,5])

用图像的形式如下：

完整代码如下：

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        int len = candidates.length; //取出数组的长度
        List<List<Integer>> res = new ArrayList<>();
        if(len==0)
        {
            return res;
        }
        Arrays.sort(candidates); //对列表进行排序

        Deque<Integer> path = new ArrayDeque<>(len);
        dfs(candidates,len,0,target,path,res); 
        return res;
    }
    private void dfs(int[] candidates, int len, int begin, int residue, Deque<Integer> path, List<List<Integer>> res)
    {
        if(residue==0) 
        //数字residue表示目标值所剩多少，我们在进行组合时用的是不断减组合中的数字，知道等于0或小于0
        {
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i=begin; i<len; i++) //这些就对应着上图的树结点的子结点
        {
            if(residue-candidates[i]<0) //这是一个剪枝过程
                break;
            if(i>begin && candidates[i]==candidates[i-1]) 
            //这一步也是剪枝过程，因为值跟前面相同，所以组合在前面一定出现过了
                continue;
            path.addLast(candidates[i]);
            dfs(candidates,len,i+1,residue-candidates[i],path,res);
            path.removeLast(); //这一步就是回溯，将上一次加入列表的值删除
        }
    }
}

题目以及解法来源

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/combination-sum-ii

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。