可视化软件开发工具/满足seo需求的网站
这是一道典型的回溯法的子集数问题。(因为可以重复，类似与图的m色问题）
每一条路径可以选择的数是candidates的每一个元素。
INPUT:
[2,3,6,7]
[7]
x= [0,0,1,-1]表示解为[2,2,3]
Solution 1:回溯法1
class Solution {public List<List<Integer>> combinationSum(int[] candidates, int target) {int t=0;int sum=0;//先排序，这样方便后面去重Arrays.sort(candidates);//每一个可行解的长度小于等于target/candidates[0]//+1是因为 解是在路径上，t只是层数，层数比解个数要多一个。比如4/1=4 maxResLen=5。//t=0，1，2，3 ，4，得1+1+1+1，此时sum=4<=target,要在进入下一层t=5，此时满足t==maxResLen，才returnint maxResLen=target/candidates[0]+1;//x保存解的下标int []x=new int[maxResLen];//解初始化为-1for(int i=0;i<maxResLen;i++)x[i]=-1;List<List<Integer>> res=new ArrayList<>();backtrack(t,candidates,target,sum,x,maxResLen,res);return res;}private void backtrack(int t,int[] candidates, int target,int sum,int []x,int maxResLen,List<List<Integer>> res){if(t==maxResLen)return;if(sum==target){List<Integer> oneRes=new ArrayList<Integer>();for(int i=0;i<maxResLen;i++){if(x[i]!=-1){oneRes.add(candidates[x[i]]);}}//去重。因为前面已经排了序，所以只有非递减的解才是不重复的int flag=1;for(int i=1;i<oneRes.size();i++){if((int)oneRes.get(i)<(int)oneRes.get(i-1))flag=0;}if(flag==1)res.add(oneRes);return;}for(int i=0;i<candidates.length;i++){//试探性先选取这个数//sum先加上 x[t]=i;sum+=candidates[i];if(sum<=target){//如果满足条件，则进入下一层backtrack(t+1,candidates,target,sum,x,maxResLen,res);//准备回溯x[t]=-1;sum-=candidates[i];}else{ //不满足条件，就还原x[t]=-1;sum-=candidates[i];}}}}
Solution 2:回溯法2
class Solution {public List<List<Integer>> combinationSum(int[] candidates, int target) {int t=0;int sum=0;Arrays.sort(candidates);int maxResLen=target/candidates[0]+1;int []x=new int[maxResLen];for(int i=0;i<maxResLen;i++)x[i]=-1;List<List<Integer>> res=new ArrayList<>();backtrack(t,candidates,target,sum,x,maxResLen,res);return res;}private boolean backtrack(int t,int[] candidates, int target,int sum,int []x,int maxResLen,List<List<Integer>> res){if(t==maxResLen-1)return false;for(int i=0;i<candidates.length;i++){//指 2 3 6 7if(sum+candidates[i]<=target){x[t]=i;//t是位置sum+=candidates[i];if(sum==target){List<Integer> oneRes=new ArrayList<Integer>();for(int j=0;j<=t;j++){if(x[j]!=-1){oneRes.add(candidates[x[j]]);}}int flag=1;for(int j=1;j<oneRes.size();j++){if((int)oneRes.get(j)<(int)oneRes.get(j-1))flag=0;}if(flag==1)res.add(oneRes);//这一层直接找到的话，就不用再进下一层了，后续不用继续执行。continue;}if(backtrack(t+1,candidates,target,sum,x,maxResLen,res)) return true;else{x[t]=-1;sum-=candidates[i]; }}}return false;}}
Solution 1:回溯法3
class Solution {public List<List<Integer>> combinationSum(int[] candidates, int target) {int t=0;int sum=0;Arrays.sort(candidates);int maxResLen=target/candidates[0]+1;int []x=new int[maxResLen];for(int i=0;i<maxResLen;i++)x[i]=-1;List<List<Integer>> res=new ArrayList<>();backtrack(t,candidates,target,sum,x,maxResLen,res);return res;}private void backtrack(int t,int[] candidates, int target,int sum,int []x,int maxResLen,List<List<Integer>> res){if(t==maxResLen-1)return;for(int i=0;i<candidates.length;i++){//指 2 3 6 7if(sum+candidates[i]<=target){x[t]=i;//t是位置sum+=candidates[x[t]];if(sum==target){List<Integer> oneRes=new ArrayList<Integer>();for(int j=0;j<=t;j++){if(x[j]!=-1){oneRes.add(candidates[x[j]]);}}int flag=1;for(int j=1;j<oneRes.size();j++){if((int)oneRes.get(j)<(int)oneRes.get(j-1))flag=0;}if(flag==1)res.add(oneRes);continue;}backtrack(t+1,candidates,target,sum,x,maxResLen,res);x[t]=-1;sum-=candidates[i]; }}return ;}}