加起来和为目标值的组合(二)

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

public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
    Arrays.sort(num);
    recur(num ,new boolean[num.length] ,target ,0 ,new ArrayList<>());
    return res;
}

public void recur(int[] num ,boolean[] flag ,int target ,int index ,ArrayList<Integer> list){

    if(target<0){
        return;
    }
    if(target==0){
        res.add(new ArrayList<>(list));
        return;
    }
    for(int i=index;i<num.length;i++){
        //!flag[i-1] 是为了保证重复数字第一次出现时可以被加进去
        if(flag[i] || (i>0 && num[i]==num[i-1] && !flag[i-1])){
            continue;
        }
        flag[i]=true;
        list.add(num[i]);
        recur(num ,flag ,target-num[i] ,i+1 ,list);
        list.remove(list.size()-1);
        flag[i]=false;
    }
}

import java.util.*;

public class Solution {
    private ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
    
    public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
        //    首先进行排序，这样能够保证输出按照非递减顺序排列 -> 【10，10，60】...
        Arrays.sort(num);
        helper(num, 0, target, new ArrayList<Integer>());
        return ans; 
    }
    
    //    搜索可行解
    private void helper(int[] num, int index, int target, ArrayList<Integer> tmp){
        //    这里采用了target - num[index]的形式求解
        //    每一轮搜索，target值都会减小，如果小于0，返回
        if(target < 0)
            return ;
        //    如果等于0，说明找到了一组可行解，将其添加到解集ans中
        if(target == 0)
            ans.add(new ArrayList<Integer>(tmp));
        
        //    从这里开始一次尝试
        for(int i = index; i < num.length; i ++){
            //    如果叠加的数值之和 + 当前值 > target，
            //    由于这组数据是排序完成的，所以不必尝试后续的数值
            //    比如：【10，10，20，50】，叠加数值之和已经超过target【80】，
            //    后续的【10，10，20，60】、【10，10，20，70】不必再尝试，即便出现重复也是如此
            if(target - num[i] < 0)
                break;
            //    希望跳过重复的解集，比如出现重复的数值【10，10，60，60，60，70】，target还是80
            //    那么，【10，10，60】只需要一组就可以了
            if(i > index && num[i] == num[i - 1])
                continue ;
            
            //    上述是排除一些明显可以不必尝试的情况，除去这部分内容，可以继续尝试搜索后续的可行解
            //    首先添加该数值到临时解集tmp中
            tmp.add(num[i]);
            //    然后尝试向后搜索
            helper(num, i + 1, target - num[i], tmp);
            //    回溯时，需要删除tmp中的最后数值【这儿可能添加了一个数值，使得整体的叠加值 > target等】
            tmp.remove(tmp.size() - 1);
        }
    }
}

import java.util.*;
public class Solution {
    ArrayList> res;
    ArrayList list;
    int target;
    int[] nums;
    public ArrayList> combinationSum2(int[] nums, int target) {
        this.res = new ArrayList();
        this.list = new ArrayList();
        this.nums = nums;
        this.target = target;
        Arrays.sort(nums);
        dfs(0,0);
        return res;
    }

    //从当前index处开始dfs，前面的累计和为sum
    public void dfs(int index,int sum){
        //剪枝，sum超过target后，不可能再匹配到target（升序）
        if(sum > target) 
            return;
        //命中target
        if(sum == target){
            res.add(new ArrayList(list));
            return;
        }
        //下一个元素的选择范围：从index到最后一个元素
       for(int i = index;i < nums.length;i++){
           //去重（重点），参考三数之和
           if(i>index && nums[i] == nums[i-1]) continue;
           //选择当前元素
           list.add(nums[i]);
           dfs(i + 1,sum + nums[i]);
           list.remove(list.size()-1);
       } 
    } 

卡时间了，之前的很多提交不能通过了，关键点在于去重操作:
if(i>index && nums[i] == nums[i-1]) continue;

import java.util.*;
public class Solution { //能过一大半，实在不行了
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    ArrayList<Integer> list = new ArrayList<>();
    int sum = 0;    //记录和
    public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
        boolean[] visited = new boolean[num.length];
        Arrays.sort(num);
        backTrack(num,target,visited,0);
        return res;
    }
    public void backTrack(int[] num,int target,boolean[] visited,int start){
        if(sum > target)    return;
        if(sum == target && !res.contains(list)){     //如果等于目标值
            res.add(new ArrayList<>(list));
            return;
        }
        for(int i = start;i < num.length;i++){
            list.add(num[i]);
            visited[i] = true;
            sum += num[i];
            
            backTrack(num,target,visited,i + 1);
            list.remove(list.size() - 1);
            sum -= num[i];
            visited[i] = false;
        }
    }
}

import java.util.*;

public class Solution {
    public ArrayList<ArrayList<Integer>> combinationSum2(int[] candidates, int target) {
        int n = candidates.length;
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if(n == 0) {
            return res;
        }
        int begin = 0;
        ArrayList<Integer> path = new ArrayList<>();
        Arrays.sort(candidates);
        dfs(candidates, target, res, begin, path);
        return res;
    }
    
    private void dfs(int[] candidates, int target, ArrayList<ArrayList<Integer>> res, int begin, ArrayList<Integer> path) {
        if(target == 0) {
            res.add(new ArrayList<>(path));
            return ;
        }
        for(int i = begin; i < candidates.length; i++) {
            if(i > begin && candidates[i] == candidates[i - 1]) {
                continue;
            }
            if(target < candidates[i]) {
                break;
            }
            target -= candidates[i];
            path.add(candidates[i]);
            dfs(candidates, target, res, i + 1, path);
            path.remove(path.size() - 1);
            target += candidates[i];
        }
    }
}

import java.util.*;
public class Solution {
    
    
    ArrayList<ArrayList<Integer>> ret=new ArrayList<>();

    public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {

        //首先排序
        Arrays.sort(num);
        dfs(num,0,target,new ArrayList<>());
        return ret;
    }
    
    public void dfs(int []num,int index,int target,ArrayList<Integer> list){
        //我们这里做减法，当target为0 返回正确结果
        if(target==0){
            ret.add(new ArrayList<>(list));
            return;
        }
        //这里进行循环
        for(int i=index;i<num.length;i++){
            //进行剪枝，当 num[i]>target的时候  肯定不能继续遍历
            if(target-num[i]<0){
                break;
            }
            //当有相等元素时候，跳过，避免重复
            if(i>index && num[i]==num[i-1]){
                continue;
            }
            //代码到这里 已经是有效答案了
            list.add(num[i]);
            //继续进行递归， 注意这里下标不是  index+1   而是  i+1，
            dfs(num,i+1,target-num[i],list);
            //回溯  这里要remove掉 
            list.remove(list.size()-1);
        }
    }

}

import java.util.*;

// 菜鸡解法
public class Solution {
    private ArrayList<ArrayList<Integer>> ansLists;
    private int[] num;
    private int target;
    
    public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
        // 组合要求不重复，需要与排列区分
        ArrayList<ArrayList<Integer>> ansLists = new ArrayList<>();
        if(num==null || num.length==0) return ansLists;
        
        this.ansLists = ansLists;
        this.num = num;
        this.target = target;
        // 排序方便防重复、剪枝
        Arrays.sort(num);
        dfs(new ArrayList<>(), -1, 0);
        
        return this.ansLists;
    }
    
    // 组合防止重复只能往后取
    public void dfs(ArrayList<Integer> list, int currIdx, int currSum) {
        if(currIdx==num.length-1 && currSum!=target) return;
        if(currSum==target) {
            ansLists.add(new ArrayList<Integer>(list));
            return;
        }
        
        for(int nextIdx=currIdx+1; nextIdx<num.length; ) {
            // 剪枝
            if(currSum+num[nextIdx]>target) break;
            // 回溯
            list.add(num[nextIdx]);
            dfs(list, nextIdx, currSum+num[nextIdx]);
            list.remove(list.size()-1);
            // 滑动到下一个不同值，防止重复
            nextIdx++;
            while(nextIdx<num.length && num[nextIdx-1]==num[nextIdx]) {
                nextIdx++;
            }
        }
    }
}

import java.util.*;
public class Solution {
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    ArrayList<Integer> ls = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
        int[] used = new int[num.length];
        Arrays.sort(num);
        dfs(num,target,used,0);      
        return res;
    }
    private void dfs(int[] a, int target,int[] used,int start){
        if(target == 0 && !res.contains(ls)) {
            res.add(new ArrayList<>(ls));
            return;
        }
        for(int i = start; i < a.length && target > 0; i++) {           
            if(used[i] == 1) continue;
            used[i] = 1;
            ls.add(a[i]);
            target -= a[i];
            dfs(a,target,used,i);
            ls.remove(ls.size()-1);
            target += a[i];
            used[i] = 0;
        }
    }
}

import java.util.*;
public class Solution {
    ArrayList<ArrayList<Integer>> arrays = new ArrayList<ArrayList<Integer>> ();
    public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
        ArrayList<Integer> array = new ArrayList<Integer>();
        if (num.length == 1 && num[0] == target){
            array.add(num[0]);
            arrays.add(array);
            return arrays;
        }
        Arrays.sort(num);
        function(num,0,num.length - 1,array,target);
        
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>> ();
      
        for (int i = 0 ; i < arrays.size() ; i++){
            if (!contains(result,arrays.get(i))){
                result.add(arrays.get(i));
            }
        }
        return result;
    }
    
    public void function(int[] arr,int start,int end,ArrayList<Integer> array,int target){
        if (!arrays.contains(array) && array.size() != 0 && sum(array) == target) {
            ArrayList<Integer> temp = new ArrayList<Integer>(array);
            Collections.sort(temp);
            arrays.add(temp);
            return;
        }
        if (sum(array) > target){
            return ;
        }
        if (start > end){
            return;
        }
        array.add(arr[start]);
        function(arr,start + 1,end,array,target);
        array.remove(array.size() - 1);
        function(arr,start + 1,end,array,target);
    }
    
    public int sum(ArrayList<Integer> array){
        int sum = 0;
        for (int i = 0 ;i < array.size() ; i++){
            sum += array.get(i);
        }
        return sum;
    }
    
    
    public boolean contains(ArrayList<ArrayList<Integer>> arrays,ArrayList<Integer> array){
        if (arrays.size() == 0){
            return false;
        }
        for (int i = 0 ; i < arrays.size() ; i ++){
            if (arrays.get(i).size() == array.size()){
                ArrayList<Integer> temp = arrays.get(i);
                Collections.sort(temp);
                Collections.sort(array);
               
                for (int j = 0 ; j < temp.size() ; j ++){
                    if (temp.get(j) != array.get(j)){
                        return false;
                    }
                }
                return true;
            }
        }
        return false;
    }
    
}