Note that different sequences are counted as different combinations.
Therefore the output is 7. Follow up: What if negative numbers are allowed in the given array? How does it change the problem? What limitation we need to add to the question to allow negative numbers?
O(n) time O(n) space memoization solution with HashMap
1 2 3 4 5 6 7 8 9 10 11 12 13 14
publicclassSolution{ Map<Integer, Integer> mem = new HashMap<>(); publicintcombinationSum4(int[] nums, int target){ if (nums == null || nums.length == 0 || target < 0) return0; if (target == 0) return1; if (mem.containsKey(target)) return mem.get(target); int combos = 0; for (int num : nums) { combos += combinationSum4(nums, target - num); } mem.put(target, combos); return combos; } }
publicclassSolution{ privateint[] counts; publicintcombinationSum4(int[] nums, int target){ counts = newint[target + 1]; Arrays.fill(counts, -1); // sometimes the combinations of a target is 0. to distinguish this, we need to set the default value to -1. counts[0] = 1; // target matches the current num return getCombination(nums, target); } publicintgetCombination(int[] nums, int target){ if (counts[target] != -1) return counts[target]; int count = 0; for (int i = 0; i < nums.length; i++) { if (target >= nums[i]){ count += getCombination(nums, target - nums[i]); } } counts[target] = count; // don't forget to update the value return count; } }
O(n) time O(n) space Bottom up DP solution
1 2 3 4 5 6 7 8 9 10 11 12 13
publicclassSolution{ publicintcombinationSum4(int[] nums, int target){ int[] counts = newint[target + 1]; counts[0] = 1; for (int i = 1; i < counts.length; i++){ for (int num : nums) { if (i - num >= 0) counts[i] += counts[i - num]; } } return counts[target]; } }
Follow-up questions
To allow negative numbers in the array, we need to limit the length of each combinations. Otherwise, the number of combinations can be infinite. Take [1, -1] and target = 1 as an example, we can have an infinite length of [1, -1, 1, -1 … 1] which sums to 1.