我一直在琢磨这个问题相当长的一段时间，由于某种原因，它是没有得到过我的头。如果我给出一个数组[1,2,3,4]，并且目标值为说5，我希望得到所有可能的组合的阵列，它们添加到目标值。

I have been pondering over this problem quite some time and for some reason it is not getting through my head. If i am given an array [1,2,3,4] and a destination value of say 5. I want to get all possible combinations from the array such that they add to the destination value.

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

So one approach i can think of is

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.

我已经看到了一些答案在网上，但他们似乎并没有什么意义，我不是在别人的答案或codeS很感兴趣，我想学习如何思考正确的做法，这样我就可以解决这样的问题。我想知道，如果有人能指导我，帮助我打破这个问题，也是我应该怎么想解决此类问题。在这一点上我并不真的很担心被效率，因为我还没有能够制定一个办法让所有的方法都是值得欢迎的。此外，我只用数组和正常的循环没有任何其他的数据结构，如哈希，因为我还没有学会preFER这些呢。

I have seen a few answers online but they do not seem to make sense and i am not really interested in others answers or codes, i want to learn how to think the correct way so i can solve such problems. i was wondering if someone can guide me and help me break down this problem and also how i should be thinking to solve such problems. I am not really worried by efficiency at this point because i have not even been able to formulate an approach so all approaches are welcome. Also i prefer using just array and normal loops not any other data structures like hash as i have not learned those yet.

推荐答案

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

Since you said you want 'ways of thinking', this is one way.

您通过先从最简单的情况各种假设

You start with simplest of cases by making various assumptions

1）假设所有的数组元素比目标值小。 - 简单的验证将有助于在实现完成

1) Assume all your array elements are smaller than the destination value. -- a simple validation will help when implementation is done.

高级步骤

您需要找出获取数的所有可能的排列方式。

You need to find out a way of obtaining all possible permutations of the number.

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

And then add each element of the permutation and check if the sum matches 'destination' (This is simpler task)

现在来这里的主要挑战：

now coming to the major challenge here:

如何获得所有可能的排列？

解决方法 让我们假设我们有一个元素的数组：的 解决办法是显而易见的：）

Solution Approach Lets assume we have an array of single element: SOlution is obvious :)

接下来，我们有两个元素的数组：的 你确定数组的大小：2 你必须遍历这个大小，因为你的组合将小于或等于该尺寸。 你的第一次迭代将有值为1，即。您正在寻找的大小为一组合 这很简单：你一个遍历数组一个

Next we have an array of two elements: You determine the size of the array: 2 You have to iterate over this size because your combinations will be less than or equal to this size. Your first iteration will have value 1. ie. you are looking for combinations of size one This is simple: you iterate over the array one by one.

下一个迭代的外观尺寸为2的组合。 因为迭代值（2）等于阵列（2）的大小，就知道只有一个可能的情况

Next iteration will look for combinations of size 2. Since the iteration value (2) is equal to size of the array (2), you know there is just one possible case.

现在，让我们处理规模3的数组：的

尺寸为1排列，你知道该怎么做。

for size 1 permutations, you know what to do.

尺寸为3排列，你知道密码是什么。

for size 3 permutations, you know what the combination is.

尺寸为2排列，则需要另一次迭代。 你遍历数组，持有大小为2的数组的数组和排列替换休息的当前元素。的

for size 2 permutations, you require another iteration. you iterate over the array, hold the current element of the array and permutate rest of the array of size 2.

接下来，您遍历大小的数组的第二个，然后第三个元素，排列替换休息（3-1 = 2）

Next you iterate over second and then third element, and permutate rest of the array of size (3-1 = 2)

--------------------------------UPDATED--------------------------------------------------

接下来让我们尝试有一个数组4个元素的 让我们称之为是A（4）

Next lets try an array having 4 elements Lets call is A(4)

有关尺寸1的排列和大小4排列，其明显的。

For size 1 permutations and size 4 permutations, its obvious.

有关尺寸3排列，你会重复你没有获得规模2排列尺寸为3的数组什么的过程。 你将举行一个元素，你将留下尺寸3 的数组。让我们把它叫做（3）

For size 3 permutations, you will repeat process of what you did for obtaining size 2 permutations for an array of size 3. You will hold one element, you will be left with an array of size 3. Let call it A(3)

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

But remember, you also need permutations of size 2. You can determine all permutations of size 2 from this array of size 3 itself by applying the same reusable component. This becomes a recursive call.

所以基本上，你必须做一件事的大部分时间。

So essentially, you have to do one thing most of the time.

如果你有大小为n的数组; A（N），则需要遍历它，持有元素被迭代，你将有规模为n-1的数组; A（N-1）

然后再进行递归调用了。 并用正1代替n中粗线

then make a recursive call again. and replace n with n-1 in the bold line

所以基本上，你看这是变成一个递归问题。

So essentially as you see this is turning into a recursive problem.

这是认为这个问题的一个解决方案的一种方式。我希望我是清楚的解释思考过程。

This is one way of thinking a solution of this problem. I hope I was clear in explaining the thinking process.

------------------------------------------Example------------------------------------------

假设我们有一个数组{1,2,3,4,5}

Assume we have an array {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 for the loop:

 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}
     }
 }

等等...

and so on...

现在让我们看一下递归调用的空运行：

now lets look at the dry run of the recursive call:

  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}
     }
 }

等等...

and so on...