Java O(2^n) non-memoized naive solution


  • 0
    M
    public class Solution {
        public int findTargetSumWays(int[] nums, int S) {
            if(nums.length<1){
                return 0;
            }
            return sum(nums, S, 0, 0, 0);
        }
        
        private int sum(int[] nums, int s, int index, int currentSum, int total){
            if(index ==  nums.length-1){
                if(currentSum + nums[index] == s){
                    if(currentSum - nums[index] == s){
                        return total+2;
                    }
                    return total+1;
                }
                if(currentSum - nums[index] == s){
                    if(currentSum + nums[index] == s){
                        return total+2;
                    }
                    return total+1;
                }
                return total;
            }
            
            return sum(nums, s, index+1, currentSum+nums[index], total) + sum(nums, s, index+1, currentSum-nums[index], total);
        }
    }
    

Log in to reply
 

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