[LeetCode]Combination Sum
題意:求一個數組中的組合為某個target的所有子數組組合,要求不重復,
思路:先將數組排序,然後按深度遍歷的思想對i - > len -1的元素進行遍歷
代碼如下:
public class Solution {
public List> combinationSum(int[] candidates, int target) {
List> results = new LinkedList>();
if(candidates == null || candidates.length ==0)return results;
Arrays.sort(candidates);//先來排個序
List temp = new LinkedList();
for(int i =0; i< candidates.length; ++i)
search(candidates, i, 0, target, results, temp);
return results;
}
/**
* 搜索函數
* @param cadidates
* @param i
* @param sum
* @param target
* @param results
* @param rs
*/
public void search(int [] cadidates, int i, int sum, int target, List> results, List rs){
if(i >= cadidates.length || sum > target) return;
else {
sum += cadidates[i];
rs.add(cadidates[i]);
if(sum == target){
List t = new LinkedList();
t.addAll(rs);
results.add(t);
}else if(sum > target){
}else {
for(int j = i ; j < cadidates.length; ++j)
search(cadidates, j, sum, target, results, rs);
}
rs.remove(rs.size()-1);
}
}
}
