Recursion with memorization + explanation of states


  • 0
    A

    The solution is to do recursion with memorization. It is obvious that we can't partition if the sum of numbers is odd. We can describe the recursion with states:

    1. pos - till what position it was calculated
    2. sum - with what sum we are at position pos
      We have two options for the number at position pos. We can add it to the first set either to the second set. Some states are repeated, so we can memorize them.

    Time complexity: O(n * k) where n is the length of array. k is the n*(maximum number(nums[i]));

    public class Solution {
        
        HashMap<State, Boolean> memory = new HashMap<>();
    
        public boolean canPartition(int[] nums) {
            if (nums.length==0) return true;
            int sum = Arrays.stream(nums).sum();
            if (sum%2==1) return false;
            return isPartitionable(nums, 0, sum/2);
        }
        
        public boolean isPartitionable(int nums [], int pos, int sum) {
            if (sum==0) return true;
            if (sum<0) return false;
            if (pos>=nums.length) return false;
            
            State state = new State(pos, sum);
            if (memory.containsKey(state)) {
                return memory.get(state);
            }
            
            boolean isPartition = false;
            if (isPartitionable(nums, pos+1, sum-nums[pos]) || isPartitionable(nums, pos+1, sum)){
                isPartition = true;
            }
            
            memory.put(state, isPartition);
            return isPartition;
        }
        
        class State {
            int pos;
            int sum;
            public State (int pos, int sum) {
                this.pos = pos;
                this.sum = sum;
            }
            
            @Override 
            public int hashCode() {
                int prime = 31;
                int result = 1;
                result = prime*result + pos;
                result = prime*result + sum;
                return result;
            }
            
            @Override
            public boolean equals(Object obj) {
                State s = (State)obj;
                return (this.pos == s.pos && this.sum == s.sum); 
            }
        }
    }
    

  • 0
    0

    @amanchik said in Recursion with memorization + explanation of states:

    Time complexity: O(n * k) where n is the length of array. k is the n*(maximum number(nums[i]));

    Could you explain how you've arrived at O(n * k) time complexity?


Log in to reply
 

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