494.目标和

两天宇宙人

2020-02-16

😂非递归DFS

非递归下，直接dfs会出现超时的情况

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        stack<pair<int, int> > stk; //值，位置
        stk.push({0, 0});
        int count = 0;
        int val, pos;
        pair<int, int> p;
        while(stk.size())
        {
            p = stk.top();
            stk.pop();
            val = p.first;
            pos = p.second;
            if(pos + 1< nums.size()) {
                stk.push({val + nums[pos], pos + 1});
                stk.push({val - nums[pos], pos + 1});
            } else {
                if(val + nums[pos] == S)
                    ++count;
                if (val - nums[pos] == S)
                    ++count;
            }
        }
        return count;
    }
};

🙂递归DFS

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        return dfs(nums, S, 0, 0);
    }
    int dfs(vector<int>& nums, int S, int val, int pos)
    {
        if(pos + 1 == nums.size()) {
            bool l = val + nums[pos] == S;
            bool r = val - nums[pos] == S;
            if(l && r)
                return 2;
            else if(l || r)
                return 1;
            return 0;
        }
        int lc = dfs(nums, S, val + nums[pos], pos + 1);
        int rc = dfs(nums, S, val - nums[pos], pos + 1);
        return rc + lc;
    }
};