[494] 目标和

回溯算法

details

递归式

var findTargetSumWays = function (nums, target) {
    let ans = 0;
    backtrack(0, 0);
    return ans;

    function backtrack(sum, index) {
        if (nums.length === index) {
            if (sum === target) {
                ans++;
            }
            return;
        }
        backtrack(sum + nums[index], index + 1);

        backtrack(sum - nums[index], index + 1);
    }
};

改成迭代写法

通过栈模拟

var findTargetSumWays = function (nums, target) {
    let ans = 0;
    let stack = [[0, 0]];
    while (stack.length > 0) {
        let [sum, i] = stack.pop();

        if (i === nums.length) {
            if (sum === target) {
                ans++;
            }
        } else {
            stack.push([sum + nums[i]], i + 1);
            stack.push([sum - nums[i]], i + 1);
        }
    }
};

时间复杂度 在这个实现中，backtrack 函数以深度优先的方式遍历 nums 的所有可能的组合，每个元素可以选择 + 或 - 的操作，因此存在 2 个选择。对于长度为 n 的数组，整个组合的数量为 2^n。这意味着：

• 时间复杂度为 $O(2^n)$，因为每个数字都可以选择加或减，生成所有可能的 2^n 种组合。

空间复杂度

• 递归的深度会达到 n，因此最差情况下递归栈的 空间复杂度为 $O(n)$。

dfs

details

var findTargetSumWays = function (nums, target) {
    const size = nums.length;
    return dfs(size - 1, target);

    function dfs(i, t) {
        if (i < 0) {
            if (t === 0) return 1;
            return 0;
        }
        return dfs(i - 1, t - nums[i]) + dfs(i - 1, t + nums[i]);
    }
};

时间复杂度分析

• 时间复杂度： $O(2^n)$
• 空间复杂度： $O(n)$

记忆优化

var findTargetSumWays = function (nums, target) {
    const memo = new Map();

    return dfs(nums.length - 1, target);

    function dfs(i, t) {
        if (i < 0) {
            return t === 0 ? 1 : 0;
        }

        const key = `${i},${t}`;
        if (memo.has(key)) {
            return memo.get(key);
        }

        const result = dfs(i - 1, t - nums[i]) + dfs(i - 1, t + nums[i]);

        memo.set(key, result);
        return result;
    }
};

空间复杂度优化

dfs 改成 dp 数组，递归改成迭代 0 1 背包问题