494. Target Sum

Link

Solution

Backtrace(DFS) /Brute force

T:( O(2^n))

We can use DP also, please check it in DP section.

   int count = 0;
    public int findTargetSumWays(int[] nums, int S) {
        
        dfs(nums, 0, S);
        return count;
    }
    
    public void dfs(int[] nums, int index, int target){
        
        if(nums.length == index){
            if(target == 0){
                count++;
            }
            return;
        }
        //all possiblities
        dfs(nums, index+1, target-nums[index]);
        dfs(nums, index+1, target+nums[index]);
    }