Question

剑指 Offer II 079. 所有子集

题目描述

给定一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

 

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

 

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• nums 中的所有元素 互不相同

 

注意：本题与主站 78 题相同： https://leetcode.cn/problems/subsets/

解法

方法一

class Solution:
  def subsets(self, nums: List[int]) -> List[List[int]]:
    res = []

    def dfs(i, n, t):
      res.append(t.copy())
      if i == n:
        return
      for j in range(i, n):
        t.append(nums[j])
        dfs(j + 1, n, t)
        t.pop()

    dfs(0, len(nums), [])
    return res

class Solution {
  public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    dfs(0, nums, new ArrayList<>(), res);
    return res;
  }

  private void dfs(int i, int[] nums, List<Integer> t, List<List<Integer>> res) {
    res.add(new ArrayList<>(t));
    if (i == nums.length) {
      return;
    }
    for (int j = i; j < nums.length; ++j) {
      t.add(nums[j]);
      dfs(j + 1, nums, t, res);
      t.remove(t.size() - 1);
    }
  }
}

class Solution {
public:
  vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> res;
    vector<int> t;
    dfs(0, nums, t, res);
    return res;
  }

  void dfs(int i, vector<int>& nums, vector<int> t, vector<vector<int>>& res) {
    res.push_back(t);
    if (i == nums.size()) return;
    for (int j = i; j < nums.size(); ++j) {
      t.push_back(nums[j]);
      dfs(j + 1, nums, t, res);
      t.pop_back();
    }
  }
};

func subsets(nums []int) [][]int {
  var res [][]int
  var t []int
  dfs(0, nums, t, &res)
  return res
}

func dfs(i int, nums, t []int, res *[][]int) {
  *res = append(*res, slices.Clone(t))
  if i == len(nums) {
    return
  }
  for j := i; j < len(nums); j++ {
    t = append(t, nums[j])
    dfs(j+1, nums, t, res)
    t = t[:len(t)-1]
  }
}

function subsets(nums: number[]): number[][] {
  const n = nums.length;
  const ans = [];
  const dfs = (i: number, t: number[]) => {
    ans.push([...t]);
    while (i < n) {
      t.push(nums[i++]);
      dfs(i, t);
      t.pop();
    }
  };
  dfs(0, []);
  return ans;
}

impl Solution {
  fn dfs(mut i: usize, t: &mut Vec<i32>, ans: &mut Vec<Vec<i32>>, nums: &Vec<i32>) {
    ans.push(t.clone());
    while i < nums.len() {
      t.push(nums[i]);
      i += 1;
      Self::dfs(i, t, ans, nums);
      t.pop();
    }
  }

  pub fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
    let mut ans = Vec::new();
    let mut t = Vec::new();
    Self::dfs(0, &mut t, &mut ans, &nums);
    ans
  }
}