C++ dfs solution


  • 0
    Y
    class Solution {
    public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int result = 0;
        dfs(nums,S,0,result);
        return result;
    }
    
    void dfs(vector<int>& nums, int target, int index, int& result){
        if(index == nums.size()){
            if(target == 0)
                result++;
            return;
        }
        dfs(nums,target - nums[index],index + 1,result);
        dfs(nums,target + nums[index],index + 1,result);
    }
    

    };


  • 0
    Z

    class Solution {
    public:
    int findTargetSumWays(vector<int>& nums, int S) {
    int res=0;
    DFS(nums,S,0,res);
    return res;
    }
    void DFS(vector<int> nums,int target,int index,int &res){
    if(index==nums.size()){
    if(target==0)res++;
    return;
    }
    DFS(nums,target-nums[index],index+1,res);
    DFS(nums,target+nums[index],index+1,res);
    }
    };
    I don't know why the code above has a TLE problem. I just change '&nums' with 'nums' in function dfs.


Log in to reply
 

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