NC233 加起来和为目标值的组合(四)

:::tips 标签：数组、递归 :::

题目描述:

给定一个由不同整数构成的数组nums和一个整数target，请你从nums中找出总和是target的组合的个数，解集中可以重复使用nums中的元素。且解集中数字顺序不同视为不同的组合。

数据范围：

数组长度不超过200，数组中的元素不超过1000，target不超过1000

示例1:

输入：[1,2,3],4
返回值：7

说明：所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

import java.util.*;

public class Solution {
    
    public int res = 0; // 定义一个整型变量，用于存放最终的返回结果
    
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int combination (int[] nums, int target) {
        // write code here
        process(nums, target);
        return res;
    }
    
    public void process(int[] nums, int reminder) {
        if (reminder == 0) {
            res++;
            return;
        }
        if (reminder < 0) {
            return;
        }
        for (int num : nums) {
            reminder -= num;
            process(nums, reminder);
            // 回溯
            reminder += num;
        }
        return;
    }
}

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param nums int整型一维数组
 * @param target int整型
 * @return int整型
 */
let res: number = 0;
export function combination(nums: number[], target: number): number {
  process(nums, target);
  return res;
}

function process(nums: number[], reminder: number) {
  if (reminder === 0) {
    res++;
    return;
  }

  if (reminder < 0) {
    return;
  }

  for (let i = 0; i < nums.length; i++) {
    const num = nums[i];
    reminder -= num;
    process(nums, reminder);
    // 回溯
    reminder += num;
  }
}