39.组合总和.md

39.组合总和

/*
 * @lc app=leetcode.cn id=39 lang=typescript
 *
 * [39] 组合总和
 */

// @lc code=start
function combinationSum(candidates: number[], target: number): number[][] {}
// @lc code=end

解法 1: 动态规划

原本想的是用 DFS,不过需要去重,太麻烦了,然后用动态规划试了下,直接过了

function combinationSum(candidates: number[], target: number): number[][] {
  const dp: number[][][] = [[[]], ...[...new Array(target)].map(() => [])]

  for (const num of candidates) {
    for (let i = num; i <= target; i++) {
      for (const arr of dp[i - num]) {
        dp[i].push([...arr, num])
      }
    }
  }
  return dp[target]
}

解法 2: DFS + 回溯

后面看了下官解,发现是自己多写了一种情况,才会导致有重复

function combinationSum(candidates: number[], target: number): number[][] {
  const res: number[][] = []
  const dfs = (path: number[] = [], sum = 0, depath = 0) => {
    if (sum === target) {
      res.push([...path])
      return
    }
    if (sum > target || depath === candidates.length) return

    dfs(path, sum, depath + 1)

    path.push(candidates[depath])
    dfs(path, sum + candidates[depath], depath)
    path.pop()
  }
  dfs()
  return res
}

Case

test.each([
  { input: { candidates: [2, 3, 6, 7], target: 7 }, output: [[7], [2, 2, 3]] },
  {
    input: { candidates: [2, 3, 5], target: 8 },
    output: [
      [2, 2, 2, 2],
      [2, 3, 3],
      [3, 5],
    ],
  },
  { input: { candidates: [2], target: 1 }, output: [] },
  { input: { candidates: [1], target: 1 }, output: [[1]] },
  { input: { candidates: [1], target: 2 }, output: [[1, 1]] },
])('input: candidates = $input.candidates, target = $input.target', ({ input: { candidates, target }, output }) => {
  expect(combinationSum(candidates, target)).toIncludeSameMembers(output)
})