78. Subsets
給定一個由唯一元素組成的整數數組 nums，返回所有可能的子集（冪集）。
解集合不得包含重複的子集。以任意順序返回解集。
範例 1：
輸入：nums = [1, 2, 3] 輸出：[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
Python
from typing import List
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
def backtrack(start: int, path: List[int]):
# Append the current path as a subset
result.append(path[:])
for i in range(start, len(nums)):
# Include nums[i] in the current subset
path.append(nums[i])
# Move on to the next element
backtrack(i + 1, path)
# Backtrack by removing the element
path.pop()
result = []
backtrack(0, [])
return result
16.72MB, 34ms
C++
#include <vector>
class Solution {
public:
std::vector<std::vector<int>> subsets(std::vector<int>& nums) {
std::vector<std::vector<int>> result;
std::vector<int> path;
backtrack(0, nums, path, result);
return result;
}
private:
void backtrack(int start, std::vector<int>& nums, std::vector<int>& path, std::vector<std::vector<int>>& result) {
// Append the current path as a subset
result.push_back(path);
for (int i = start; i < nums.size(); ++i) {
// Include nums[i] in the current subset
path.push_back(nums[i]);
// Move on to the next element
backtrack(i + 1, nums, path, result);
// Backtrack by removing the element
path.pop_back();
}
}
};
8.15MB, 0ms
Javascript
/**
* @param {number[]} nums
* @return {number[][]}
*/
var subsets = function(nums) {
const result = [];
const backtrack = (start, path) => {
// Append the current path as a subset
result.push([...path]);
for (let i = start; i < nums.length; i++) {
// Include nums[i] in the current subset
path.push(nums[i]);
// Move on to the next element
backtrack(i + 1, path);
// Backtrack by removing the element
path.pop();
}
};
backtrack(0, []);
return result;
};
52.4MB, 75ms
