组合总和（中等题）

39. 组合总和

难度中等1200

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

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

说明：

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

示例 1：

输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
  [7],
  [2,2,3]
]

示例 2：

输入：candidates = [2,3,5], target = 8,
所求解集为：
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

提示：

• 1 <= candidates.length <= 30
• 1 <= candidates[i] <= 200
• candidate 中的每个元素都是独一无二的。
• 1 <= target <= 500

自己做的暴力算法

class Solution {
    private List<List<Integer>> ans=new ArrayList<>(); //存储答案列表

    public  List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<Integer> tempList=new ArrayList<>();
        calc(candidates, target,tempList,0);
        return ans;
    }

    public Integer calc(int[] candidates, int target, List<Integer> tempList,int start){

        int sum=0;
        for(Integer val:tempList){//计算当前已经加入的和
            sum+=val;
        }

        if(sum>=target){//如果和已经大于目标了，返回
            return sum;
        }

        for(int i=start;i<candidates.length;i++){
            tempList.add(candidates[i]);
            Integer val=test(candidates,target,tempList,i);

            if(val==target){
                List<Integer> tempAns=new ArrayList<>(tempList);
                ans.add(tempAns);
            }
            tempList.remove(tempList.size()-1);
        }


        return target+1;//终止条件
    }
}

大佬的写法，先排序，效率提升了不少

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> listAll=new ArrayList<List<Integer>>();
        List<Integer> list=new ArrayList<Integer>();
        //排序
        Arrays.sort(candidates);
        find(listAll,list,candidates,target,0);
        return listAll;
    }
    public void find(List<List<Integer>> listAll,List<Integer> tmp,int[] candidates, int target,int num){
        //递归的终点
        if(target==0){
            listAll.add(tmp);
            return;
        } 
        if(target<candidates[0]) return;
        for(int i=num;i<candidates.length&&candidates[i]<=target;i++){
            //拷贝一份，不影响下次递归
            List<Integer> list=new ArrayList<>(tmp);
            list.add(candidates[i]);
            //递归运算，将i传递至下一次运算是为了避免结果重复。
            find(listAll,list,candidates,target-candidates[i],i);
        }   
    } 
}

赏

谢谢你请我吃糖果

微信