Skip to content

Latest commit

 

History

History

038. Combination Sum

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 

这道题很啰嗦,条件又很多,例子还容易让人误解。有种摸不着头脑的感觉。

我稍微提炼一下:

一个正数数组,一个正数,从数组中摘出若干数(可重复提取),但摘出的数组成的数组应为一个非递减序列。 且所有摘出的数组不得有重复。

然后再来看看例子:[2,3,6,7], 7

我们如何查找符合条件的数组呢?模拟一下咱们大脑的思路:

// 从 2 开始, 因为允许重复摘取,所以先不断重复 2
2,2,2 // 到这里 sum = 6,如果再取 2,则为 8,已经超过了目标值 7.
// 既然 2不行,那么开始往后寻找 3,6,7 等,显然,都不符合。
// 于是我们退一步,重复两遍 2 ,然后第三个数从 3 开始
2,2,3 // 这时 sum = 7, 恰好为我们的目标值,这个数组便是我们想要的一组。
// 后续可以尝试 6,7,显然都不符合。
// 继续我们的思路,从 一个 2 开始。
2,3 // 这时 sum = 5, 如果再取 3 ,则为8, 超过目标值 7.
// 重复 3 不行,后续呢,6,7,显然超了。
// 仍然继续
3,3 // 此刻 sum = 6, 再来 3 一定不行。后面的6,7 显然也不行。
// 再来的话,就是6 开头,显然没戏。
7 // 此刻 sum = 7, 再次符合咱们的要求。 记录之。

经过上面的过程,我们就得出了需要的数组:[2,2,3] 和 [7]。且不会存在重复,且数组必然是按照非递减的顺序来的。

这样的思维过程是非常朴素的穷举策略,一个个的尝试,但尝试的过程中遇到错误,如 sum > 7 ,就会放弃,就像是试错法。其实在算法理论中,这样的思想有一个专有的名字,叫做回溯法。

更准确的,这样的一个搜索过程,应该称之为 DFS (深度优先搜索)。

有人会奇怪,说回溯是很正常的,但 DFS 从何说起,DFS 的核心思想难道不是,不能两次踏入同一条河 吗?

的确, DFS 的不能重复,和我们这里 “摘出的数组不可重复”一致,但与目标数组的元素不可重复无关。在这个问题里, DFS 跳出的条件也应该是与重复无关的,应该是 sum > target 这个条件,更为合适。

可以尝试写出 dfs 函数:

void dfs(const vector<int> &cdds, int target, vector<int> curr, int index, vector<vector<int>> ret) {
    // 上述参数,首先参考原题中的参数,然后 curr 是摘出的那个数组,index 是指从哪个元素开始,ret 自然是返回的数组集合了。
    if (!target) { ret.push_back(curr); return; } // 如果 target 成为 0,即恰好找到匹配的数组,存入 ret.
    for (int i=index; i<cdds.size(); ++i) { // 为何从 index 开始,因为要求摘出数组保持非递减。
        if (cdds[i] <= target) { // 否则,跳出
            curr.push_back(cdds[i]);
            dfs(cdds, target-cdds[i], curr, i, ret);
            curr.pop_back(); // 这一步就是上面咱们“退一步”的那个点,即回溯。
        } else break;
    }
}

DFS 非常常用,但如果仅仅记住定义,并不能发现它的踪迹,只有把握其思想,才可以在类似这样的“枚举迷宫题”中合理运用它。