首页 > 代码库 > [LeetCode] Add to List 39. Combination Sum Java

[LeetCode] Add to List 39. Combination Sum Java

题目:Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.

 

For example, given candidate set [2, 3, 6, 7] and target 7
A solution set is: 

[
  [7],
  [2, 2, 3]
]

题意及分析:给出一个数组和一个目标量target,求出由数组元素组成的数组和等于target的所有可能(数组中的元素可以复用),数组所有元素都为正整数,不能包含相同的数组。这道题要求出所有可能,所以可以使用回溯的方法。我们用一个start变量存储子数组开始的位置,用int remian保留target减去当前求值数组的和,这样我们就可以转化为 在start和candidates.length-1中求 和等于target的数组。理解不够深入,讲得不是很清楚,具体可以看一下代码。。

代码:

 

public class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<Integer> array= new ArrayList<>();
        List<List<Integer>> list = new ArrayList<>();
        int start=0;
        int remain=target;
        backTracking(list,array,candidates,start,remain);
        return list;
    }
	
	public void backTracking(List<List<Integer>> list,List<Integer> array,int[] candidates,int start,int remain) {
		if(remain<0)
			return;
		else if(0==remain){	//有解
			list.add(new ArrayList<>(array));
		}else{
			for(int i=start;i<candidates.length;i++){
				if(i>0&&candidates[i]==candidates[i-1]) continue;  //这一步操作主要是去重
				array.add(candidates[i]);
				backTracking(list, array, candidates, i, remain-candidates[i]);    //这里注意一下是i,因为元素可以重复利用
				array.remove(array.size()-1);
			}
		}
		return;
	}
}

 

  

 

[LeetCode] Add to List 39. Combination Sum Java