Skip to content

377. Combination Sum IV

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.

The test cases are generated so that the answer can fit in a 32-bit integer.

Example 1:

Input: nums = [1,2,3], target = 4
Output: 7
Explanation:
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.

Example 2:

Input: nums = [9], target = 3
Output: 0

Constraints:

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 1000
  • All the elements of nums are unique.
  • 1 <= target <= 1000

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?

Solution:

class Solution {
    public int combinationSum4(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();

        List<Integer> subResult = new ArrayList<>();
        int curSum = 0;

        backtracking(curSum, nums, target, subResult, result);
        return result.size();
    }

    private void backtracking(int curSum, int[] nums, int target, List<Integer> subResult, List<List<Integer>> result){

        if (curSum == target){
            result.add(new ArrayList<>(subResult));
            return;
        }



        if (curSum == target){
            result.add(new ArrayList<>(subResult));
            return;
        }

        if (curSum > target){
            return;
        }

        for(int i = 0; i < nums.length; i++){
            subResult.add(nums[i]);
            backtracking(curSum + nums[i], nums, target, subResult, result);
            subResult.remove(subResult.size() - 1);
        }

        return;
    }
}

// TC: O(k^n)
// SC: O(n)
// TLM

Recursion + Memoization

class Solution {
    public int combinationSum4(int[] nums, int target) {
        // 创建一个数组用于记忆化
        int[] memo = new int[target + 1];
        // 用 -1 初始化数组,表示这些结果还未计算过
        Arrays.fill(memo, -1);
        memo[0] = 1; // 达成目标和为0的唯一组合方式是选取空集

        // 开始递归回溯
        return backtrack(nums, target, memo);
    }

    private int backtrack(int[] nums, int target, int[] memo) {
        // 如果目标值为负数,直接返回0,因为没有合法的组合
        if (target < 0) {
            return 0;
        }

        // 如果我们已经计算过这个目标值的结果,直接返回存储的值
        if (memo[target] != -1) {
            return memo[target];
        }

        // 计算所有可以组成当前目标值的组合
        int result = 0;
        for (int num : nums) {
            result += backtrack(nums, target - num, memo);
        }

        // 将结果存储在memo数组中
        memo[target] = result;
        return result;
    }
}

DP

class Solution {
    public int combinationSum4(int[] nums, int target) {
        // Create a dp array where dp[i] represents the number of ways to get sum i
        int[] dp = new int[target + 1];
        dp[0] = 1; // There is exactly one way to achieve target sum 0 (by choosing nothing)

        // Iterate through each sum from 1 to target
        for (int i = 1; i <= target; i++) {
            // For each number in nums, if we can use that number to reach sum i,
            // add the number of ways to make sum (i - num) to dp[i]
            for (int num : nums) {
                if (i - num >= 0) {
                    dp[i] += dp[i - num];
                }
            }
        }

        // The answer is the number of ways to make the target sum
        return dp[target];
    }
}