C++ solutions: dfs / dp


  • 0
    C
    class Solution {
    public:
    /**method one dfs**//*
        int dfs_count;
        int target;
        void dfs(vector<int>& nums,int i,int sum){
            if(i==nums.size()){
                if(sum==target){
                    dfs_count++;
                }
                return ;
            }
            dfs(nums,i+1,sum+nums[i]);
            dfs(nums,i+1,sum-nums[i]);
            return ;
        }
        int findTargetSumWays(vector<int>& nums, int S) {
            dfs_count = 0;
            target = S;
            dfs(nums,0,0);
            return dfs_count;
        }
    */
    
    /**method two dp**/
        int findTargetSumWays(vector<int>& nums, int S) {
            unordered_map<int,int> sum;
            sum[0] = 1;
            for(auto i : nums){
                unordered_map<int,int> tem_sum;
                for(auto j : sum){
                    tem_sum[j.first+i] += j.second;
                    tem_sum[j.first-i] += j.second;
                }
                sum = std::move(tem_sum);
            }
            return sum[S];
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.