Sharing my 1ms Java solution

  • 0

    Idea is same as the solution posted by @FreeTymeKiyan .

    It helps to imagine the overlapping sub problems-

    1. Consider you come up with a recursive solution which maintains the value needed to reach the target.
    2. Run this on the input [1,2,3] and target = 4. For the sake of understanding imagine you also maintain a list of integers that contribute to the current sum.
      When we reach <1,1,1,1> we get our 1st result.
    3. It's important to note that each element comes from 1 recursive call. When our last recursive call finishes, we have found the number of ways to get to a sum of 1. Similarly when the 2nd last call finishes, we know the number of ways to get to a sum of 2.
    4. These values will be used for future states like
      <1,2> will use no of ways to get to a sum of 1
      <2> will use no of ways to get to a sum of 2
    5. This can be maintained by a 1-d array dp where dp[x] denotes the number of ways to get to a sum of x.
    6. Also naturally as this is a TOP DOWN approach, most time is saved at the TOP levels.

    Couple of minor details-

    1. I always sort the array to make sure I do not make any wasteful calls-
      If my list is <1,1,1,1> and target is 4. Then I do not go to state <1,1,1,2>
    2. The above condition also eliminates the base case where the current sum is greater than the target.

    Here is my code-

    public int combinationSum4(int[] nums, int target) {
            int[] dp = new int[target + 1];
            Arrays.fill(dp, -1);
            return helper(nums, target , dp);
        private int helper(int[] nums, int needed, int[] dp){
            if(needed == 0)
                return 1;
            if(dp[needed] != -1)
                return dp[needed];
            int combinations = 0;
            for(int i = 0; i < nums.length; i++){
                if(nums[i] > needed) break;
                combinations += helper(nums, needed - nums[i] , dp);
            dp[needed] = combinations;
            return combinations;

Log in to reply

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