组合求和问题

输入：一个无序数组，一个目标和
输出：数组中目标和的组合
要求：结果中不含重复组合
用例：[2,3,6,7],7 ===> [ [7] [2,2,3] ]

分析

这个也没啥分析的。从一头开始一个个加进去，看还剩多少，再加。直到剩的为0或者小于0为止。

思路

回溯法。
关键在于回溯。
再加上迭代。就ok

代码

package day_7;
// 这是要写一个迭代。
// 或者是用 dfs（Deep First Search)
// 无奈 迭代 你用的很差 从这一个算法开始学一下吧
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CombinationSum {
    public List<List<Integer>> combinationSum(int[] candidates, int target){
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(candidates==null || candidates.length==0)
            return res;
        Arrays.sort(candidates); // 先排升序
        helper(candidates,target,0,new ArrayList<Integer>(),res);
        return res;
    }

    private void helper(int[] candidates,int target, int start, ArrayList<Integer> item, List<List<Integer>> res){
        if(target == 0){
            // 这时候做一步去重
            if(!res.contains(item)) res.add( new ArrayList<Integer>(item));  // 这里注意写法。要写 new array list(item) 因为这里的 item 在后面回溯还要用。 
// 相当于把当前的Item 重新申请了空间，复制了一份。 不这样做的话，最终的 item 指向的空间对应的数是空的。因为后面有回溯的步骤。
            return;
        }

        if(target < 0) return; // 这是迭代的结束条件，很重要

        //剩下的就是 target>0 的情况
        for( int i=start ; i<candidates.length; i++){
            item.add(candidates[i]);
            helper(candidates,target-candidates[i],i,item,res);
            item.remove(item.size()-1);  // 这是回溯法很重要的 一步 回溯。即每次删除最后的一个来看
        }

    }

    public static void main(String[] args){
        int a[] = {2,3,5};
        CombinationSum c = new CombinationSum();
        System.out.println(c.combinationSum(a,8));
    }
}