LeetCode刷题笔记-回溯法-组合总和问题

题目描述：

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum

Java代码实现

    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
　　　　　List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates); //升序排序，便于剪枝
        combine2(result,new ArrayList<>(),candidates,target,0);
        return result;
    }

public static void combine2(List<List<Integer>> result,List<Integer> temp,int[] candidates,int target,int begin){
        if (target==0){
            result.add(new ArrayList<>(temp));
            return;
        }

        for (int i=begin;i<candidates.length && target-candidates[i] >=0 ;i++){
            temp.add(candidates[i]);
            combine2(result,temp,candidates,target-candidates[i],i);
            temp.remove(temp.size()-1);
        }
    }

 

posted on 2019-06-22 16:50 野生学霸 阅读(…) 评论(…) 编辑 收藏

版权声明：本文为sqchao原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/sqchao/p/11069464.html