组合总和（combinationSum）以及List的add（）方法的问题

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。
解集不能包含重复的组合。

思路：用回溯法，把candidates中的数先加一下，如果不行则回溯。

设计递归函数combination，根据JAVA参数引用传递的特点，实现遍历。

我的代码：

public class CombinationSum {
	public List<List<Integer>> combinationSum(int[] candidates, int target) {
		List<List<Integer>> res = new ArrayList<>();
		if(candidates.length == 0
				||(candidates.length == 1 && candidates[0]>target))
			return res;
        Arrays.sort(candidates); //排序
        combination(res, target, 0, null, candidates);
		return res;
    }
	private void combination(List<List<Integer>> res,int target,int i,List<Integer>tmp,int[] candidates) {
		if(target == 0) {
            //此处一定要新建一个List再添加到res中，因为java的list.add()
            //方法是传递的引用！！！如果直接将tmp加进去后续对tmp的add、remove操作
            //会影响到res中的值，使得结果不对！！！
			List<Integer> tmp1 = new ArrayList<>(tmp);
			if(!res.contains(tmp1))
				res.add(tmp1);
			//找到满足条件的解，回溯找其他解
			tmp.remove(tmp.size()-1);
			return;
		}else if (target<0) {
			//不满足条件，且子节点必然也不满足条件，回溯
			tmp.remove(tmp.size()-1);
			return;
		}
		for(;i<candidates.length;i++) {
			if(tmp == null)tmp = new ArrayList<>();
			//由于candidates是排好序的，如果出现比target大，则后续都剪掉（相当于剪枝）
			if(candidates[i]>target)break; 
			tmp.add(candidates[i]);
			combination(res, target-candidates[i], i, tmp, candidates);	
		}
		//能够执行到这里说明这个节点解空间的所有子树都遍历过并且没有找到满足条件的解，需要回溯
		if(!tmp.isEmpty())
			tmp.remove(tmp.size()-1);
	}

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

另外一种写法：也是回溯法。

//count用来计数每个数记录了几次
private void search(int[] candidates, int target, int[] count, List<List<Integer>> res, int n) {
        if(target == 0) {
            List<Integer> list = new ArrayList<Integer>();
            for(int i = 0; i <= n; i++) {
                for(int j = 0; j < count[i]; j++) {
                    list.add(candidates[i]);
                }
            }
            res.add(list);
        }
        
        if(n == candidates.length || target < candidates[n])
            return;
        
        search(candidates, target, count, res, n + 1);
        count[n]++;        
        search(candidates, target - candidates[n], count, res, n);
        count[n]--;
    }
    
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        if(candidates == null || candidates.length == 0) {
            return new ArrayList<List<Integer>>();
        }
        
        Arrays.sort(candidates);
        
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        int[] count = new int[candidates.length];
        search(candidates, target, count, res, 0);
        return res;
    }

组合总和（combinationSum）以及List的add（）方法的问题

相关推荐