返回与目标匹配的数组之和的递归代码

Question

以下代码显示了等于数组中目标的所有可能总和，我的问题是我理解它在第一个答案中如何工作的逻辑，但是我不明白递归如何工作以使卡再次相同并检查更多结果（更多数组），并且以与组合数组“清理”相同的方式，如果它在递归操作后执行此操作，请尝试桌面测试和 chatGPT，但我根本无法理解它在整个过程中是如何工作的。

function findSums(nums, target) {
    function findSum(target, start, combination) {
        
        if (target === 0) {
            result.push([...combination]);
            return;
        }
        for (let i = start; i < nums.length; i++) {
            console.log('i: ',i,'start: ',start,'n1:',nums[i],'n2:',nums[i-1]);

            if (i > start && nums[i] === nums[i - 1]) {                
                continue;
            }
            findSum(target - nums[i], i + 1, combination);
            combination.pop();
        }
    }
    nums.sort((a, b) => a - b);
    let start = 0;
    let combination = [];
    let result = [];
    findSum(target, start, combination);
    return result;
}
console.log(findSums([1, 3, 2, 4, 5], 6));

我希望你能帮助我理解这段代码是如何工作的。我认为我最大的困惑在于 for 中的递归调用，而且我也不明白为什么在某个时刻“i”变得与“start”不同

Answer 1

让我尝试通过逐步分解代码来帮助您理解代码，尤其是递归部分：

findSums

函数基本上用于查找

nums

数组中所有唯一的数字组合，这些组合加起来等于给定的

target

。它通过使用在

findSum

内部定义的辅助函数

findSums

来实现此目的。

以下是

findSum

函数的实际作用：

基本情况：如果

target

为0，则表示当前的

combination

数字加起来是原来的

target

。然后将该组合添加到

result

数组中，函数返回。

递归情况：函数从

nums

索引开始迭代

start

数组。对于索引

i

处的每个数字，它检查该数字是否可以是加起来等于

target

的组合的一部分。

避免重复：如果当前数字与前一个数字相同且

i

大于

start

，则会跳过该数字以避免重复组合。

递归调用：使用新目标

findSum

、新起始索引

(target - nums[i])

和当前数字组合对

(i + 1)

进行递归调用。

回溯：递归调用后，通过调用

combination

删除最后添加到

combination.pop()

的数字。这是回溯步骤，允许函数尝试不同的组合。

我希望你明白

findSum

函数实际上在这里做什么:) 现在让我回答您的一些具体问题：

1。递归如何工作才能使卡片再次相同并检查更多结果（更多数组）？

递归实际上是通过使用不同的参数调用相同的函数来工作的。在这种情况下，将使用缩小的目标和递增的起始索引来调用

findSum

函数。每个递归调用都独立于其他调用，并且具有自己的执行上下文。这意味着

combination

数组和其他变量对于每次调用都是唯一的。

2。如果在递归操作之后执行此操作，组合数组如何“清理”？

组合数组通过

combination.pop()

操作“清理”。这发生在递归调用返回之后。它删除了递归调用之前添加的最后一个元素，有效地撤消了最后一步并允许循环尝试下一个数字。

3。为什么在某个点“i”变得与“start”不同？

变量

i

与

start

不同，因为

start

是函数应开始考虑

nums

数组中的数字的索引，而

i

是循环中的当前索引。随着循环的进行，

i

递增，但

start

保持不变，直到下一次递归调用，将其设置为

i + 1

。这确保每个组合使用不同的元素并避免重复使用相同的元素。

这是一个输入

[1, 3, 2, 4, 5]

和

target

6 的示例：

对数组进行排序：

[1, 2, 3, 4, 5]

从 0 处的空组合

[]

和

start

开始。 尝试将

1

添加到组合中并调用

findSum(5, 1, [1])

。 在新的呼叫中，尝试将

2

添加到组合中并呼叫

findSum(3, 2, [1, 2])

。 在新的呼叫中，尝试将

3

添加到组合中并呼叫

findSum(0, 3, [1, 2, 3])

。 由于目标现在为 0，因此将

[1, 2, 3]

添加到结果中并返回。 通过从组合中弹出

3

回溯并尝试下一个数字。 继续此过程，直到尝试了所有组合。 每个递归调用都会探索搜索空间中的不同路径，回溯可确保考虑所有可能的组合。

start

参数对于避免重复并确保每个组合都是唯一的至关重要。