LeetCode 40. Combination Sum II (Java版; Medium)

偏执的太偏执、 2023-07-14 10:36 12阅读 0赞

### [welcome to my blog][] ###

## LeetCode 40. Combination Sum II (Java版; Medium) ##

#### 题目描述 ####

Given a collection of candidate numbers (candidates) and a target number (target), find all unique
    combinations in candidates where the candidate numbers sums to target.
    
    Each number in candidates may only be used once in the combination.
    
    Note:
    
    All numbers (including target) will be positive integers.
    The solution set must not contain duplicate combinations.
    Example 1:
    
    Input: candidates = [10,1,2,7,6,1,5], target = 8,
    A solution set is:
    [
      [1, 7],
      [1, 2, 5],
      [2, 6],
      [1, 1, 6]
    ]
    Example 2:
    
    Input: candidates = [2,5,2,1,2], target = 5,
    A solution set is:
    [
      [1,2,2],
      [5]
    ]

#### 第一次做; 回溯; 核心: 1)先对数组进行排序, 方便去重 2) 去重有两种方法, 一种是使用HashSet, 容易想, 但是占用空间, 另一种是使用条件判断, 见注释 ####

class Solution { 
        public List<List<Integer>> combinationSum2(int[] candidates, int target) { 
            List<List<Integer>> res = new ArrayList<>();
            //核心: 为了去重, 需要对数组尽心排序
            Arrays.sort(candidates);
            core(candidates, 0, target, res, new ArrayList<Integer>());
            return res;
        }
    
        private void core(int[] arr, int index, int target, List<List<Integer>> res, List<Integer> list){ 
            //base case
            if(target==0){ 
                res.add(new ArrayList<Integer>(list));
                return;
            }
            if(target<0){ 
                return;
            }
            //
            HashSet<Integer> set = new HashSet<>();
            for(int i=index; i<arr.length; i++){ 
                int cur = arr[i];
                //同一级, 不能有重复元素, 比如说, 在本次递归函数中已经选取过1了, 就不能再选取1了; (注意数组已经排好序)
                //不同级, 可以有重复元素, 比如说, 上次递归函数中选取了1, 这次还可以选取1
                //核心: 如何区分重复是发生在同一级还是不同级的情况呢? 下面这个条件判断很巧妙, 但是不容易想到, 
                //例子{1,1,1,6}, 下面的判断不允许同一级出现多次1, 但是允许不同级出现重复1
                // if(i>index && cur == arr[i-1]){ 
                // continue;
                // } //使用HashSet最简单, 但是费空间
                if(set.contains(cur)){ 
                    continue;
                }
                set.add(cur);
    
                //选(错误的分析)
                list.add(cur);
                core(arr, i+1, target-cur, res, list); //新递归从i+1开始,这样就不会重复选择arr[i]
                list.remove(list.size()-1);
    
                //不选(错误的分析); 在回溯中,可处理的元素并不是只有一个, 而是有好几个, 对于这好几个元素来说, 每一个都要选择一次, 所以需要通过循环处理; 
                //但是并不能理解成选或者不选, 在回溯中, 是必须选取一个元素!
                // core(arr, i+1, target, res, list);
            }
        }
    }

[welcome to my blog]: https://littlehaes.com