Combination Sum IV 377

Description

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

nums = [1, 2, 3] target = 4

The possible combination ways are: (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1)

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?

Credits: Special thanks to @pbrother for adding this problem and creating all test cases.

Hint

how many results ? DP problem

Method

it is bag problem target can increase from 0 - val each time add 1 find if there are number can make f[i] + k = val

f[i] += f[k]; find(i - k) in array

Time & Space

o(n^2)

Code

public class Solution {
    public int combinationSum4(int[] nums, int target) {
           if (target < 0 || nums == null || nums.length == 0){
               return 0;
           }
           int[] f = new int[target + 1];
           f[0] = 1;
           for (int i = 0; i <= target; i++){
                for (int k = 0; k < i; k++){
                     if (find(nums, i - k)){
                         f[i] += f[k];
                     }
                }
           }
           return f[target];
    }

    public boolean find(int[] nums, int val){
           for (int j = 0; j < nums.length; j++){
                if (nums[j] == val){
                    return true;
                }
           }
           return false;

}

public int combinationSum4(int[] nums, int target) { if (target < 0 || nums == null || nums.length == 0){ return 0; } int[] f = new int[target + 1]; f[0] = 1; Arrays.sort(nums); for (int i = 0; i <= target; i++){ for (int j = 0; j < nums.length; j++){ if (nums[j] > i){ break; } else if (nums[j] == i){ f[i] += 1; } else { f[i] += f[i - nums[j]]; }

           }
       }
       return f[target];
}

public int combinationSum4(int[] nums, int target) {
           if (target < 0 || nums == null || nums.length == 0){
               return 0;
           }
           int[] f = new int[target + 1];
           f[0] = 1;
           Arrays.sort(nums);
           for (int i = 0; i <= target; i++){
               for (int j = 0; j < nums.length; j++){
                     if (nums[j] > i){
                         break;
                     } else if (nums[j] == i){
                         f[i] += 1;
                     } else {
                         f[i] += f[i - nums[j]];
                     }

               }
           }
           return f[target];
    }