组合求和问题
输入：一个无序数组，一个目标和
输出：数组中目标和的组合
要求：结果中不含重复组合
用例：[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));
}
}
