LeetCode - 494. 目标和

494. 目标和

给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例 1:

解题思路： 深度优先搜索，维护一个路径的和值，然后当路径遍历完毕后，比较和值是否等于目标值，如果相同，则得到一个符合目标值的路径。

// DFS, time:O(2^n), space:O(n)
class Solution {
public:
    void helper(vector<int>& nums, int start, int out, int S, int& res) {
        if (start >= nums.size()) {
            if (S == out) ++res;
            return;
        }
        helper(nums, start + 1, out + nums[start], S, res);
        helper(nums, start + 1, out - nums[start], S, res);
    }
    int findTargetSumWays(vector<int>& nums, int S) {
        int res = 0;
        helper(nums, 0, 0, S, res);
        return res;
    }
};