Java, dp solution


  • 0
    D
    public class Solution {
        public int combinationSum4(int[] nums, int target) 
        {
            // sort nums
            Arrays.sort(nums);
            int[] res = new int[target + 1];
            // init
            res[0] = 0;
            // dp
            for (int i = 1; i < res.length; i++)
            {
                for (int j = 0; j < nums.length; j++)
                {
                    if (i > nums[j]) { res[i] += res[i - nums[j]]; }
                    else if (i == nums[j]) { res[i] += 1;}
                    // because we sort before, no need to continue if i < nums[j];
                    else break;
                }
            }
            
            return res[target];
        }
    }
    

Log in to reply
 

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