JAVA recursion solution using HashMap as memory.


  • 35

    The DP solution goes through every possible sum from 1 to target one by one.
    Using recursion can skip those sums that are not the combinations of the numbers in the given array. Also, there is no need to sort the array first.

    public class Solution {
        Map<Integer, Integer> map = new HashMap<>();
        public int combinationSum4(int[] nums, int target) {
            int count = 0;
            if (nums == null || nums.length ==0 || target < 0 ) return 0;
            if ( target ==0 ) return 1;
            if (map.containsKey(target)) return map.get(target);
            for (int num: nums){
                count += combinationSum4(nums, target-num);
            }
            map.put(target, count);
            return count;
        }
    }
    

  • 0
    D

    @yubad2000 good example of illustrating top-down approach to avoid unnecessary cases!


  • 1
    J

    excellent memorize search. However, try not to use global variable.


  • 1
    J

    Same idea, top-down dp solution, but I improved the code a little bit.

    public int combinationSum4(int[] nums, int target) {
            // Write your code here
            if (nums == null || nums.length == 0 || target <= 0) {
                return 0;
            }
            HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
            map.put(0, 1);
            search(nums, target, map);
            return map.get(target);
        }
        
        private int search(int[] nums, int sum, HashMap<Integer, Integer> map) {
            if (sum < 0) {
                return 0;
            }
            if (map.containsKey(sum)) {
                return map.get(sum);
            }
            int res = 0;
            for (int i = 0; i < nums.length; i++) {
                sum -= nums[i];
                if (map.containsKey(sum)) {
                    res += map.get(sum);
                } else {
                    res += search(nums, sum, map);
                }
                sum += nums[i];
            }
            map.put(sum, res);
            return map.get(sum);
        }
    

  • 0
    T

    Why does using int array instead of hash map time out?


  • 0
    J

    @taymas How do you use int array? Have an array the length equaling to the sum? If the sum is very large, you use too much extra memory.


  • 0
    I

    How does it ensure not to use the same element in nums array twice?


  • 0
    I

    sorry, just realized you can actually use it twice


  • 0
    O

    Thanks! May I ask what is the time complexity of this memorize search? Thanks!


  • 0

    @taymas The int actually works well. Check the comments in my code as below.

    public class Solution {
        private int[] t;
        public int combinationSum4(int[] nums, int target) {
            this.t = new int[target+1];
            Arrays.fill(t, -1); //highlight 1: The default value 0 could not work since you can not tell whether it is a non-solution or it has not been caculated.
            t[0]=1; //highlight 2: The very initial case is target is 0, means there are some value in the array equals to the target. So return 1.
            return incursive(nums, target);
        }
    
        private int incursive(int[] nums, int target){
            if(t[target]!=-1) return t[target];
            int count = 0;
            for(int n:nums){
                if(target>=n) count += incursive(nums, target-n);
            }
            t[target] = count;
            return count;
        }
    }
    

Log in to reply
 

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