求组合和求排列的区别

组合不强调元素之间的顺序，排列强调元素之间的顺序

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

求组合：零钱兑换 II

题目详情

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

代码实现

function change(amount: number, coins: number[]): number {
  const dp = new Array(amount + 1).fill(0);
  dp[0] = 1;
  //先循环遍历物品，再循环遍历背包
  for (let i = 0; i < coins.length; i++) {
    for (let j = coins[i]; j <= amount; j++) {
      dp[j] += dp[j - coins[i]];
    }
  }
  return dp[amount];
}

求排列：组合总和 Ⅳ

题目详情

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

代码实现

function combinationSum4(nums: number[], target: number): number {
  const dp: number[] = new Array(target + 1).fill(0);
  dp[0] = 1;
  //先循环遍历背包，再循环遍历物品
  for (let i = 0; i <= target; i++) {
    for (let num of nums) {
      if (i >= num) dp[i] += dp[i - num];
    }
  }
  return dp[target];
}