78. Subsets
문제 설명
중복없는 정수 배열 nums가 주어질 때, 가능한 모든 subsets를 반환하세요.
정답에는 중복된 subsets가 있어서는 안됩니다. 어떠한 정렬로도 반환할 수 있습니다.
해결 방법
모든 조합을 구하는 문제로, 재귀에 들어갈 때마다 item을 넣고, answer에 넣는 과정을 끝까지 반복하면 된다.
이 문제는 기존 조합 문제를 조금만 변형시키면 풀 수 있기 때문에 사실상 어려운건 없다.
풀이 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
function subsets(nums: number[]): number[][] {
const answer: number[][] = [[]];
const dfs = (comb: number[], depth: number): void => {
for (let i = depth; i < nums.length; i++) {
comb.push(nums[i]);
dfs(comb, i + 1);
answer.push([...comb]);
comb.pop();
}
};
dfs([], 0);
return answer;
}
테스트 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
describe('78. Subsets', () => {
test('example test 1', () => {
const output = subsets([1, 2, 3]);
const expected = expectAnyOrder([
[],
[1],
[2],
[1, 2],
[3],
[1, 3],
[2, 3],
[1, 2, 3],
]);
expect(output.length).toBe(expected.length);
expect(output).toEqual(expect.arrayContaining(expected));
});
test('example test 2', () => {
const output = subsets([0]);
const expected = expectAnyOrder<number>([[], [0]]);
expect(output.length).toBe(expected.length);
expect(output).toEqual(expect.arrayContaining(expected));
});
});
구현 후
테스트코드를 작성할 때 배열에 정렬이 상관없는 경우 arrayContaining을 사용했는데, 이때까지 잘못사용하고 있었다는 것을 알았다. arrayContaining은 말 그대로 배열 안에 비교 요소가 있기만 하면 테스트를 통과시켜준다. 예를 들어, [1, 2].toEqual(expect.arrayContaining([1]))이와 같은 테스트케이스가 있으면 해당 테스트 케이스는 통과하는 것이다. 그렇기 때문에 비상대책으로 배열의 길이를 비교하는 검증을 추가했고, 추후 더 좋은 방법이 있는지 찾아봐야겠다.