JavaScript中combinationSum函数返回空元素数组的问题排查

问题根源 #

你遇到的问题核心在于JavaScript的数组是引用类型：当执行resultArr.push(ds)时，并没有把当前ds的内容复制存入结果数组，而是存了指向这个数组的引用。后续回溯过程中的ds.pop()操作会直接修改这个数组的内容，等最终返回结果时，之前存入的数组已经被清空，所以输出[[], []]。

而console.log(ds)能看到正确结果，是因为执行push时ds刚好处于符合条件的状态，还没来得及执行后续的pop操作。

修复方案 #

将ds推入结果数组时，创建当前数组的副本而非直接推入原数组。常用的创建副本方式有两种：

• 展开运算符：[...ds]
• 数组slice()方法：ds.slice()

修改后的代码 #

var combinationSum = function(candidates, target) {
    const resultArr = []
    function combinationSumHelper(idx, candidates, ds, target){
        if(idx === candidates.length){ // base case
            if(target === 0){
                console.log(ds)
                // 改为推入数组副本
                resultArr.push([...ds])
            }
            return
        }
        if(candidates[idx] <= target){
            ds.push(candidates[idx])
            combinationSumHelper(idx, candidates, ds, target - candidates[idx])
            ds.pop()
        }
        combinationSumHelper(idx+1, candidates, ds, target)
    }
    combinationSumHelper(0, candidates, [], target)
    return resultArr
};

console.log(combinationSum([2,3,6,7], 7)) // 输出：[[2,2,3],[7]]

内容的提问来源于stack exchange，提问作者Ankit Verma