思路:先将数组排序,然后按深度遍历的思想对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); } } }