给出一个数字和一个数组，找到所有可能的组合，它们加起来等于给定的数字的原理是什么

问题描述

在一次采访中有人问我这个计划。给该任务一个整数数组作为输入，另一个数字为target，找到数组中所有累加到给定目标的组合。

示例：

array = [1,2,1,1,1]
target = 3

expected result : [1,2],[1,1,1],[2,1],[2,1]

我想出了以下代码：

public static void main(String args[]) {
    Integer[] numbers = { 1, 2, 1, 1, 1 };
    int target = 3;
    process(numbers, target);
}

private static void process(Integer[] numbers, int target) {
    for (int i = 0; i 

但是此代码仅打印3种组合：[1 2], [2 1], [1 1 1]

正确的方法是什么？还有其他更好的解决方案。

思路一：

您可以使用回溯来做类似的事情：

  public List> combinationSum(int[] candidates, int target) {
    List> result = new ArrayList();
    List temp = new ArrayList();
    Arrays.sort(candidates);
    int start = 0; 

    backtrack(candidates, target, start, result, temp);

    return result;
}

public void backtrack(int[] candidates, int remaining, int start, List> result, List temp) {
    if(remaining == 0) { 
        result.add(new ArrayList(temp)); 
        return;
    }

    if(remaining 

您可以阅读有关回溯和类似方法的更多信息。

思路二：

这也是使用递归的最佳选择：

public static void main(String args[]) {
    Integer[] numbers = { 1, 2, 1, 1, 1 };
    int target = 3;

    for(int i = 0; i (), 0, target);
    }
}

private static void recurseAdd(int currentIndex, Integer[] numbers, List usedNumbers, int sum, int target) {
    if (currentIndex >= numbers.length) {
        return;
    }

    sum = sum + numbers[currentIndex];
    usedNumbers.add(numbers[currentIndex]);

    if (sum == target) {
        System.out.println(usedNumbers);
        return;
    }

    if (sum > target) {
        return;
    }

   for (int i = currentIndex + 1; i (usedNumbers), sum, target);
    }
}

 以上内容就是爱站技术频道小编为大家分享的给出一个数字和一个数组，找到所有可能的组合，它们加起来等于给定的数字的原理是什么，看完以上分享之后，大家应该都知道这个原理是什么了吧。