LeetCode40-组合总数II

一、题目描述

二、回溯树

组合是典型的求一个数列的子集问题，题目中的限制是找出的数列不能重复，那么这个也很简单，只需要将原序列进行升序排序即可，在回溯树横向扩展的时候（for循环），将重复的元素直接跳过即可（不进行递归，具体看代码）

三、组合总数II代码实现

class Solution {
    
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    
        List<List<Integer>> res = new ArrayList<>();
        // 这里必须要先排序，因为要去重
        Arrays.sort(candidates);
        solve(candidates, target, res, new ArrayList<>(), 0, 0);
        return res;
    }

    public void solve(int[] candidates, int target, List<List<Integer>> res, List<Integer> curRes, int startIndex, int curSum) {
    
        if (curSum == target) {
    
            // 需要进行记录
            res.add(new ArrayList<>(curRes));
            return;
        } 

        if (curSum > target) {
    
            return;
        }

        for (int i = startIndex; i < candidates.length; i++) {
    
            if (curSum + candidates[i] > target) {
    
                break;
            }
            // 从第一个之后，需要判断是否需要进行去重
            if (i > startIndex) {
    
                // 横向去重
                if (candidates[i] == candidates[i - 1]) {
    
                    continue;
                }
            }
            curSum += candidates[i];
            curRes.add(candidates[i]);
            solve(candidates, target, res, curRes, i + 1, curSum);
            curSum -= candidates[i];
            curRes.remove(curRes.size() - 1);
        }
    }
}