组合篇 ​

const combine = (n, k) => {
  const ret = []
  const dfs = (path, idx) => {
    if (path.length === k) {  // 回溯树中的第K层
      ret.push([...path])
      return
    }
    if (path.length > k) return  // 剪枝
    for (let i = idx; i <= n; i++) {
      path.push(i)
      dfs(path, i + 1)
      path.pop()
    }
  }
  dfs([], 1)
  return ret
}

const combinationSum = (nums, target) => {
  const [ret, len] = [[], nums.length]
  let sum = 0
  const dfs = (path, idx) => {
    if (sum === target) {
      ret.push([...path])
      return
    }
    if (sum > target) return  // 剪枝
    for (let i = idx; i < len; i++) {
      path.push(nums[i])
      sum += nums[i]
      dfs(path, i)  // 允许重复选择
      path.pop()
      sum -= nums[i]
    }
  }
  dfs([], 0)
  return ret
}

const combinationSum2 = (nums, target) => {
  const [ret, len] = [[], nums.length]
  let sum = 0
  nums.sort((a, b) => a - b)
  const dfs = (path, idx) => {
    if (sum === target) {
      ret.push([...path])
      return
    }
    if (sum > target) return  // 剪枝
    for (let i = idx; i < len; i++) {
      // 跳过重复元素
      if (i > idx && nums[i] === nums[i - 1]) continue
      path.push(nums[i])
      sum += nums[i]
      dfs(path, i + 1)  // 不允许重复选择
      path.pop()
      sum -= nums[i]
    }
  }
  dfs([], 0)
  return ret
}