Algorithm
Problem Name: 78. Subsets
Given an integer array nums of unique elements, return all possible subsets (A subset of an array is a selection of elements (possibly none) of the array.) (the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
Example 1:
Input: nums = [1,2,3] Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Example 2:
Input: nums = [0] Output: [[],[0]]
Constraints:
1 <= nums.length <= 10-10 <= nums[i] <= 10- All the numbers of
numsare unique.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
typedef struct {
int **p;
int *csz;
int psz;
int pn;
} res_t;
void add2res(res_t *res, int *buff, int d) {
if (d) {
int *tmp = malloc(d * sizeof(int));
//assert(tmp);
memcpy(tmp, buff, d * sizeof(int));
res->p[res->pn] = tmp;
} else {
res->p[res->pn] = NULL;
}
res->csz[res->pn ++] = d;
}
void bt(int *nums, int sz, int start, res_t *res, int *buff, int d) {
int i;
add2res(res, buff, d);
for (i = start; i < sz; i ++) {
buff[d] = nums[i];
bt(nums, sz, i + 1, res, buff, d + 1);
}
}
int** subsets(int* nums, int numsSize, int** columnSizes, int* returnSize) {
res_t res = { 0 };
int *buff, i;
res.psz = 1 << numsSize;
res.p = malloc(res.psz * sizeof(int *));
res.csz = malloc(res.psz * sizeof(int));
//assert(res.p && res.csz);
buff = malloc(numsSize * sizeof(int));
//assert(buff);
bt(nums, numsSize, 0, &res, buff, 0);
free(buff);
*columnSizes = res.csz;
*returnSize = res.pn;
return res.p;
}
Input
nums = [1,2,3]
Output
[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector < vector<int>>res;
backtrack(nums, 0, vector<int>(), res);
return res;
}
void backtrack(vector<int>& nums, int k, vector<int> subset, vector < vector<int>>& res){
if(k == nums.size()){
res.push_back(subset);
return;
}
backtrack(nums, k+1, subset, res);
subset.push_back(nums[k]);
backtrack(nums, k+1, subset, res);
}
};
Input
nums = [1,2,3]
Output
[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public List();
List curr = new ArrayList<>();
int n = nums.length;
Arrays.sort(nums);
helper(nums, 0, n, ans, curr);
return new ArrayList < >(ans);
}
private void helper(int[] nums, int idx, int n, List curr) {
ans.add(new ArrayList<>(curr));
if (idx >= n) {
return;
}
for (int i = idx; i < n; i++) {
if (i > idx && nums[i] == nums[i - 1]) {
continue;
}
curr.add(nums[i]);
helper(nums, i + 1, n, ans, curr);
curr.remove(curr.size() - 1);
}
}
}
Input
nums = [0]
Output
[[],[0]]
#4 Code Example with Javascript Programming
Code -
Javascript Programming
function subsets(nums) {
const list = [];
const len = nums.length;
const subsetNum = Math.pow(2, len);
for (let n = 0; n < subsetNum; n++) {
list[n] = [];
}
for (let i = 0; i < len; i++) {
for (let j = 0; j < subsetNum; j++) {
if ((j >> i) & 1) {
list[j].push(nums[i]);
}
}
}
return list;
}
console.log(subsets([1, 2, 3]));
Input
nums = [0]
Output
[[],[0]]
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = [[]]
for num in nums:
res += [item+[num] for item in res]
return res
Input
nums = [1,2,3]
Output
[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
#6 Code Example with C# Programming
Code -
C# Programming
using System;
using System.Collections.Generic;
namespace LeetCode
{
public class _078_Subsets
{
public IList < IList<int>> Subsets(int[] nums)
{
var results = new List < IList<int>>();
results.Add(new List < int>());
if (nums == null || nums.Length == 0) { return results; }
Array.Sort(nums);
int i, j, n = nums.Length, number = 1 << nums.Length, temp;
for (i = 1; i < number; i++)
{
var result = new List<int>();
temp = i;
for (j = 0; j < n; j++)
{
if ((temp & 1) == 1) { result.Add(nums[j]); }
temp >>= 1;
}
results.Add(result);
}
return results;
}
}
}
Input
nums = [1,2,3]
Output
[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]