Subsets (M)
題目
Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:
Input: nums = [1,2,3]
Output:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
題意
求一個陣列的冪集(即所有子集，包括全集和空集，構成的集族)，
思路
回溯法，
也可以利用位運算來求子集，具體方法參考 LeetCode 78. Subsets （位運算入門：利用位運算求子集），
也可以直接回圈迭代處理，
代碼實作
Java
回溯法
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
subsets(nums, 0, new ArrayList<>(), ans);
return ans;
}
private void subsets(int[] nums, int index, List<Integer> list, List<List<Integer>> ans) {
if (index == nums.length) {
ans.add(new ArrayList<>(list));
return;
}
subsets(nums, index + 1, list, ans);
list.add(nums[index]);
subsets(nums, index + 1, list, ans);
list.remove(list.size() - 1);
}
}
位運算
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
List<Integer> list = new ArrayList<>();
int all = 1 << (nums.length); // 總情況數
for (int i = 0; i < all; i++) {
// 判斷陣列中每一個數是否應該添加
for (int j = 0; j < nums.length; j++) {
if ((i & (1 << j)) > 0) {
list.add(nums[j]);
}
}
ans.add(new ArrayList<>(list));
list.clear();
}
return ans;
}
}
JavaScript
回溯法
/**
* @param {number[]} nums
* @return {number[][]}
*/
var subsets = function (nums) {
let lists = []
dfs(nums, 0, [], lists)
return lists
}
let dfs = function (nums, index, list, lists) {
if (index === nums.length) {
lists.push([...list])
return
}
dfs(nums, index + 1, list, lists)
list.push(nums[index])
dfs(nums, index + 1, list, lists)
list.pop()
}
位運算
/**
* @param {number[]} nums
* @return {number[][]}
*/
var subsets = function (nums) {
let lists = []
let count = 1 << nums.length
for (let i = 0; i < count; i++) {
let list = []
for (let j = 0; j < nums.length; j++) {
if (i & (1 << j)) {
list.push(nums[j])
}
}
lists.push([...list])
}
return lists
}
迭代
/**
* @param {number[]} nums
* @return {number[][]}
*/
var subsets = function (nums) {
let lists = [[]]
for (let i = 0; i < nums.length; i++) {
let size = lists.length
for (let j = 0; j < size; j++) {
lists.push(lists[j].concat(nums[i]))
}
}
return lists
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/21310.html
標籤：其他