给定数组中的元素可以找到与目标值相等的组合

Question

我思考这个问题已经有很长一段时间了，但由于某种原因，我没有想到它。如果给我一个数组[1，2，4]和一个目标值，比如5。我想从数组中获得所有可能的组合，以便它们添加到目标值中。

所以我能想到的一种方法是

1!=5
1+2!=5
1+3!=5
1+4=5
//now check with combos of 3 digits.
1+2+3 !=5
1+2+4 !=5
//now check with combos of 4...however at this point i realized i missed the combination 1+3+4 also.

我在网上看到了一些答案，但它们似乎没有意义，我对其他人的答案或代码也不太感兴趣，我想学习如何正确思考，这样我就能解决这些问题。我想知道是否有人能指导我，帮助我解决这个问题，以及我应该如何思考来解决这些问题。在这一点上，我真的不担心效率，因为我甚至还没能制定出一种方法，所以所有的方法都是受欢迎的。此外，我更喜欢只使用数组和普通循环，而不是像hash这样的任何其他数据结构，因为我还没有学会这些。

Answer 1

既然你说你想要"思维方式"，这是一种方式。

您从最简单的情况开始，进行各种假设

1） 假设所有数组元素都小于目标值。——实现完成后，简单的验证将有所帮助。

高级步骤

你需要找到一种方法来获得所有可能的数字排列。

然后添加排列的每个元素，并检查总和是否与"目的地"匹配（这是一个更简单的任务）

现在面临的主要挑战是：

如何获得所有可能的排列

解决方案 假设我们有一个单一元素的数组：解决方案显而易见：）

接下来我们有一个由两个元素组成的数组：您可以确定数组的大小：2你必须迭代这个大小，因为你的组合将小于或等于这个大小。第一次迭代的值为1。你在找一号的组合这很简单：一个接一个地迭代数组。

下一次迭代将寻找大小为2的组合。由于迭代值（2）等于数组（2）的大小，所以您知道只有一种可能的情况。

现在让我们处理大小为3的数组：

对于1号排列，你知道该怎么做。

对于大小3的排列，你知道组合是什么。

对于大小为2的排列，您需要另一次迭代。迭代数组，保持数组的当前元素，并置换大小为2的数组的其余部分。

接下来，迭代第二个元素，然后迭代第三个元素，并置换大小为（3-1=2）的数组的其余部分

----------------------------------更新--------------------------------------------------------

接下来让我们尝试一个具有4个元素的数组让我们呼叫A（4）

对于大小1的排列和大小4的排列，这是显而易见的。

对于大小3的排列，您将重复您为大小3的数组获得大小2的排列所做的过程。您将持有一个元素，您将留下一个大小为3的数组。我们称之为A（3）

但请记住，您还需要大小为2的排列。您可以通过应用相同的可重用组件，从这个大小为3的数组本身确定大小为2的所有排列。这变成了一个递归调用。

所以从本质上讲，大多数时候你必须做一件事。

'如果您有一个大小为n的数组；A（n），您需要对其进行迭代，保持元素正在迭代，您将获得大小为n-1的数组；A（n-1）'

然后再次进行递归调用。并在粗线中将n替换为n-1

因此，正如你所看到的，本质上这正在变成一个递归问题。

这是解决这个问题的一种思路。我希望我能清楚地解释思考的过程。

---------------------------------------------示例--------------------------------------------

假设我们有一个数组｛1,2,3,4,5｝

我们的功能看起来像

 function G (int[] array ) {
   Looping over array{ 
       remove array[index] from array
        you are left with restOfTheArray .// store it some where.
       then
          make a recursive call to G with restOfTheArray; 
     }
 }

环路干运行：

 Dry run 1:
  funtion G (Array (n ) ) {
    Looping over {1,2,3,4,5}{ 
        first value while looping is 1, remove it from the array;
        you have {2,3,4,5}.// store it some where.
       then
          make a recursive call to G with {2,3,4,5}
     }
 } 

  Dry run 2: 
funtion G (Array (n ) ) {
   Looping over {1,2,3,4,5}{ 
       second value while looping is 2, remove it from the array;
        you have {1,3,4,5}.// store it some where.
       then
          make a recursive call to G with {1,3,4,5}
     }
 }

等等…

现在让我们来看看递归调用的试运行：

  Dry Run 1.1
 funtion G (Array (n ) ) {
   Looping over {1,2,3,4,5}{ 
       First value while looping is 1, remove it from the array;
        you have {2,3,4,5}.// store it some where.
       then
          make a recursive call to G with {2,3,4,5}
     }
 }
 Dry Run 1.2 
 funtion G (Array (n ) ) {
   Looping over {2,3,4,5}{ 
       First value while looping is 2, remove it from the array;
        you have {3,4,5}.// store it some where.
       then
          make a recursive call to G with {3,4,5}
     }
 }

等等…