78.子集.md

78.子集

/*
 * @lc app=leetcode.cn id=78 lang=typescript
 *
 * [78] 子集
 */

// @lc code=start
function subsets(nums: number[]): number[][] {}
// @lc code=end

解法 1: 递归

function subsets(nums: number[]): number[][] {
  const res: number[][] = []
  const dfs = (nums: number[], path: number[] = [], start = 0) => {
    if (nums.length === start) {
      res.push(path)
      return
    }

    dfs(nums, [...path], start + 1)
    path.push(nums[start])
    dfs(nums, [...path], start + 1)
  }
  dfs(nums)

  return res
}

解法 2: 回溯

function subsets(nums: number[], path: number[] = [], start = 0, res: number[][] = []): number[][] {
  res.push([...path])
  for (let i = start; i < nums.length; i++) {
    path.push(nums[i])
    subsets(nums, [...path], i + 1, res)
    path.pop()
  }
  return res
}

解法 3: 回溯 2

function subsets(nums: number[]): number[][] {
  const res: number[][] = []
  const dfs = (path: number[], set: Set<number>) => {
    res.push([...path])
    for (const num of [...set]) {
      if (num < path[path.length - 1]) continue
      path.push(num)
      set.delete(num)
      dfs(path, set)

      // 回溯
      set.add(num)
      path.pop()
    }
  }

  dfs([], new Set(nums))
  return res
}

解法 4: 位运算

function subsets(nums: number[]): number[][] {
  const n = nums.length
  const res: number[][] = new Array(1 << n).fill(0).map(() => [])
  for (let i = 0; i < 1 << nums.length; i++) {
    for (let j = 0; j < nums.length; j++) {
      if (i & (1 << j)) res[i].push(nums[j])
    }
  }
  return res
}

Case

test.each([
  {
    input: { nums: [1, 2, 3] },
    output: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]],
  },
  { input: { nums: [0] }, output: [[], [0]] },
])('input: nums = $input.nums', ({ input: { nums }, output }) => {
  expect(subsets(nums)).toIncludeSameMembers(output)
})