문제
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], [] ]
풀이
우선 조합의 경우의 수를 구해야 하므로 순열의 경우에서 오름차순인것만 골라내서 결과배열에 넣도록 한다.
경우의수를 걸러낼때 처음에는 배열을 사용해서 간단하게 풀었다. 근데 메모리를 많이 잡아먹어서 이번엔 비트마스크로 한번 풀어보았다.
근데 그래도 메모리를 많이 잡아먹는데, 아마 비트마스크를 숫자로 변환하는 과정에서 사용하는 배열때문에 그런게 아닌가 싶다..
다음에 한번더 고민해서 다시 풀어보자.
/**
* @param {number[]} nums
* @return {number[][]}
*/
const bitmaskToNumbers = (bitmask, nums) => {
const temp = [];
for (let i = 0; i < nums.length; i++) {
if ((1 << i) & bitmask) temp.push(nums[i]);
}
return [...temp];
};
var subsets = function(nums) {
if (!nums.length) return [];
else if (nums[0] === 0) return [[], [0]];
const result = [];
const dfs = (index, bitmask) => {
if (index > nums.length) return;
result.push(bitmaskToNumbers(bitmask, nums));
for (let i = index; i < nums.length; i++) {
bitmask |= 1 << i;
dfs(i + 1, bitmask);
bitmask ^= 1 << i;
}
};
dfs(0, 0);
return result;
};결과
시간은 괜찮은데 메모리가 너무 많이 잡아먹었다..
