组合总和

题目形容：给定一个无反复元素的数组 candidates 和一个指标数 target ，找出 candidates 中所有能够使数字和为 target 的组合。

candidates 中的数字能够无限度反复被选取。

阐明：

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

示例阐明请见LeetCode官网。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

解法一：穷举法
相似结构一棵多叉树，最大深度为candidates数组的长度，而后获取所有可能的门路，最大门路是由根节点到叶子节点，判断所有的门路之和是否等于target，如果相等，则加到后果集中，最初须要判重，把反复的组合去掉，最初返回。
import java.util.*;public class LeetCode_039 {    /**     * 穷举法     *     * @param candidates     * @param target     * @return     */    public static List<List<Integer>> combinationSum(int[] candidates, int target) {        // 后果集        List<List<Integer>> result = new ArrayList<>();        // 所有可能的组合状况        Queue<List<Integer>> allPossibleCombinations = new LinkedList<>();        // 初始化所有的状况        for (int candidate : candidates) {            List<Integer> onePossibleCombination = new ArrayList<>();            onePossibleCombination.add(candidate);            allPossibleCombinations.add(onePossibleCombination);        }        while (!allPossibleCombinations.isEmpty()) {            List<Integer> temp = allPossibleCombinations.poll();            int sum = 0;            for (Integer num : temp) {                sum += num;            }            if (sum == target) {                result.add(temp);            } else if (sum < target) {                for (int candidate : candidates) {                    // List复制办法                    List<Integer> toAdd = new ArrayList<>(Arrays.asList(new Integer[temp.size()]));                    Collections.copy(toAdd, temp);                    toAdd.add(candidate);                    allPossibleCombinations.add(toAdd);                }            }        }        // 去重后的后果        List<List<Integer>> result1 = new ArrayList<>();        for (int i = 0; i < result.size(); i++) {            boolean isRepeated = false;            List<Integer> one = result.get(i);            Collections.sort(one);            for (int j = i + 1; j < result.size(); j++) {                List<Integer> two = result.get(j);                Collections.sort(two);                if (one.size() != two.size()) {                    continue;                }                boolean equals = true;                for (int x = 0; x < one.size(); x++) {                    if (!one.get(x).equals(two.get(x))) {                        equals = false;                        continue;                    }                }                if (equals) {                    isRepeated = true;                }            }            if (!isRepeated) {                result1.add(one);            }        }        return result1;    }    public static void main(String[] args) {        int[] candidates = new int[]{8, 10, 6, 3, 4, 12, 11, 5, 9};        for (List<Integer> integers : combinationSum(candidates, 28)) {            for (Integer integer : integers) {                System.out.print(integer + " ");            }            System.out.println();        }    }}
【每日寄语】 不要急着让生存给予所有的答案，有时咱们须要急躁的期待。置信过程，坦然前行，不负生存，生存也必不负你。