Java Short DFS Solution


  • 16

    This is a pretty easy problem. Just do DFS and try both "+" and "-" at every position. Easy version of Expression Add Operators https://leetcode.com/problems/expression-add-operators/

    public class Solution {
        int result = 0;
    	
        public int findTargetSumWays(int[] nums, int S) {
            if (nums == null || nums.length == 0) return result;
            helper(nums, S, 0, 0);
            return result;
        }
        
        public void helper(int[] nums, int target, int pos, long eval){
            if (pos == nums.length) {
                if (target == eval) result++;
                return;
            }
            helper(nums, target, pos + 1, eval + nums[pos]);
            helper(nums, target, pos + 1, eval - nums[pos]);
        }
    }
    

    Optimization: The idea is If the sum of all elements left is smaller than absolute value of target, there will be no answer following the current path. Thus we can return.

    public class Solution {
        int result = 0;
    	
        public int findTargetSumWays(int[] nums, int S) {
            if(nums == null || nums.length == 0) return result;
            
            int n = nums.length;
            int[] sums = new int[n];
            sums[n - 1] = nums[n - 1];
            for (int i = n - 2; i >= 0; i--)
                sums[i] = sums[i + 1] + nums[i];
            
            helper(nums, sums, S, 0);
            return result;
        }
        public void helper(int[] nums, int[] sums, int target, int pos){
            if(pos == nums.length){
                if(target == 0) result++;
                return;
            }
            
            if (sums[pos] < Math.abs(target)) return;
            
            helper(nums, sums, target + nums[pos], pos + 1);
            helper(nums, sums, target - nums[pos], pos + 1);
        }
    }
    

  • 0
    H

    @shawngao Thank you for your solution. I am doing the exact same thing in Python. I have no idea why I am getting Time Limit Exceeded! Can you help with that? Here is my code:

    class Solution(object):
        def findTargetSumWays(self, nums, S):
            """
            :type nums: List[int]
            :type S: int
            :rtype: int
            """
            return self.find_target(nums,S,0)
    
        def find_target(self,nums,S,i):
            if i == len(nums):
                if S == 0:
                    return 1
                else:
                    return 0
            else:
                return self.find_target(nums,S+nums[i],i+1) + self.find_target(nums,S-nums[i],i+1)
    

  • 0
    S

    @shawngao and @harshaneel Even I have the same problem getting a TLE

     def findTargetSumWays(self, nums, S):
            """
            :type nums: List[int]
            :type S: int
            :rtype: int
            """
            return self.findingways(nums,S,0)
            
        def findingways(self,nums,S,index) :
            if index >= len(nums) :
                if S == 0 : 
                    return 1
                else : 
                    return 0
            
            return self.findingways(nums,S - nums[index] , index + 1 ) + self.findingways(nums,S + nums[index] , index + 1 )
       
    

  • 1

    @sankalp6 @harshaneel Hmmm... Your solutions look correct. Maybe Python is slower than Java...


  • 1
    H

    @sankalp6 @shawngao I did some research about it and I think I know now why that happens. Python is a dynamic language, unlike Java. Java has Tail Recursion Optimization which is optimized by the compiler. Follow this thread from StackOverflow for more info. In my implementation, there is tail recursion which makes this super slow.

    Something to keep in mind for next time.


  • 1

    @sankalp6 @harshaneel I added an optimization to my original post. The idea is If the sum of all elements left is smaller than absolute value of target, there will be no answer following the current path. Then we can return.
    The runtime of Java solution decreased from ~800ms to ~300ms. You may try that in Python.


  • 0

    @harshaneel, the JVM doesn't have any tail call optimization (could point you to StackOverflow, but that would be ironic in this case :p)


  • 4

    Short naive DFS solution without global variable. Thanks for sharing!

        public int findTargetSumWays(int[] nums, int S) {
            return dfs(nums, 0, S, 0);
        }
        
        private int dfs(int[] nums, int sum, int target, int k) {
            if (nums.length == k) {
                return sum == target ? 1 : 0;
            }
            return dfs(nums, sum + nums[k], target, k + 1) + 
                    dfs(nums, sum - nums[k], target, k + 1);
        }
    

  • 0

    @shawngao said in Java Short DFS Solution:

    @sankalp6 @harshaneel I added an optimization to my original post. The idea is If the sum of all elements left is smaller than absolute value of target, there will be no answer following the current path. Then we can return.
    The runtime of Java solution decreased from ~800ms to ~300ms. You may try that in Python.

    Your first approach is obviously O(2^n) time algorithm, just wondering what's time complexity of your 2nd approach.


Log in to reply
 

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