给定数组中的元素找到等于目标值的组合

Question

我一直在思考这个问题很长一段时间，并且由于某种原因，它没有经过我的头脑。如果我给了一个数组[1,2,3,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. 

我已经看到了一些答案在线，但他们似乎没有什么意义，我不想在别人的答案或代码很感兴趣，我想学习如何思考正确的方式，以便我可以解决这些问题。我想知道是否有人可以指导我，帮助我分解这个问题，以及我应该如何解决这些问题。在这一点上，我并不十分担心效率，因为我甚至没有能够制定一个方法，所以所有的方法都是受欢迎的。另外我更喜欢使用数组和正常循环，而不是像哈希那样的其他数据结构，因为我还没有学到这些。

Answer 1

既然你说你想'想法'，这是一种方法。

您通过使各种假设

1）假设你所有的数组元素比目标值小先从最简单的情况。 - 一个简单的验证将有助于实施完成。

你需要找出获得号码的所有可能的排列方式

高级步骤。

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

现在来这里的主要挑战：

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

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

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

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

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

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

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

对于大小为2的排列，您需要进行其他迭代。 你迭代阵列之上，保持尺寸的数组的数组和尺寸2.

接下来遍历第二和第三然后元件阵列的排列替换休息，休息排列替换的当前元素（3 -1 = 2）

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

Next让我们尝试一个有4个元素的数组 让我们打电话是A（4）

对于1号大小排列和4号大小排列，其显而易见。

对于大小为3名的排列，你会重复你做了什么获得大小为2个排列尺寸为3 你将举行一个元素的数组过程中，你会留下大小3的数组。我们称之为A（3）

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

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

'如果您有一个大小为n的数组; A（n），你需要迭代它，保持迭代元素，你将有一个大小为n-1的数组; A（n-1）'

然后再次进行递归调用。 并用粗体行中的n-1代替n

因此，基本上如您所见，这正在变成一个递归问题。

这是一种思考此问题的解决方案。我希望我在解释思考过程中很清楚。

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

假设我们有一个数组{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} 
    } 
} 

等等...