494. Target Sum

發表於 | 分類於

problem

solution

  • backtracking

    O(2^N) time 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    class Solution {
    public:
        vector<string> ret;
        void backtracking(vector<int>& nums, int i,string  path, int sum, int target){
            if(i==nums.size()){
                if(sum == target) ret.push_back(path);
                return;
            }
            backtracking(nums, i+1, path+"+"+to_string(nums[i]), sum+nums[i], target);
            backtracking(nums, i+1, path+"-"+to_string(nums[i]), sum-nums[i], target);
            
        }
        int findTargetSumWays(vector<int>& nums, int target) {
            int n = nums.size();
            string path;
            backtracking(nums, 0, path,0, target);
            return ret.size();
            
            
        }
    };

option 1 - backtracking

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int ret =0;
    void backtracking(vector<int>& nums, int i, int sum, int target){
        if(i==nums.size()){
            if(sum == target) ret++;
            return;
        }
        
        backtracking(nums, i+1, sum+nums[i], target);
        backtracking(nums, i+1,  sum-nums[i], target);
        
    }
    int findTargetSumWays(vector<int>& nums, int target) {
        int n = nums.size();
        backtracking(nums, 0,0, target);
        return ret;
        
    }
};

option 2 - memo pattern

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    unordered_map<string, int>  memo;
    int backtracking(vector<int>& nums, int i, int sum, int target){
        if(i==nums.size()){
            if(sum == target)  return 1;
            return 0;
        }
        string key = to_string(i)+ "," + to_string(sum);
        
        if(memo.find(key)!=memo.end()) return memo[key];
        int val = 0;
        val+=backtracking(nums, i+1,  sum+nums[i], target);
        val+=backtracking(nums, i+1,  sum-nums[i], target);

        return memo[key] = val;
        
    }
    int findTargetSumWays(vector<int>& nums, int target) {
        int n = nums.size();
        return backtracking(nums, 0,0, target);        

    }
};

analysis