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:
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];
}
}