작성
·
217
0
지금의 코드의 경우 flag 제거하면
[1,3,5,7] = [6,10] / [1,5,10] = [3,6,7]
인 부분집합만 판별을 하던데요 (이 두가지 케이스만 걸림
([6,10] = [1,3,5,7] / [1,3,5,7] = [6,10]이런식으로 순서 바뀐것까지 포함해서 4가지인데 결국 2개나 마찬가지)
[1,6] = [7]
이런 케이스는 판별이 안되는데..
그렇다면 지금 코드가 완벽하지 않을수도 잇다는 생각이
드는데요
지금 코드로도 어떤 케이스든 다 판별이 가능한게 맞을까요?
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡfunction solution(arr) {
let answer = [];
let check = Array.from({length:arr.length},()=>0);
function DFS(idx) {
if(idx === arr.length) {
let temp = [];
let temp2 = [];
for(let i=0; i<check.length; ++i) {
if(check[i] === 1) temp.push(arr[i]);
else temp2.push(arr[i]);
}
let sum1 = temp.reduce((acc,v)=>{return acc + v;},0)
let sum2 = temp2.reduce((acc,v)=>{return acc + v;},0)
if(sum1 === sum2)
answer.push('YES');
}else {
check[idx] = 1;
DFS(idx+1);
check[idx] = 0;
DFS(idx+1);
}
}
DFS(0);
//* 부분집합 64개 만들기
//* 서로소인 집합을 추리기 -
//* 서로소인 집합의 합을 비교해서 같은 대상이 잇나 검색
}
let arr=[1, 3, 5, 6, 7, 10];
console.log(solution(arr));
답변 1
0
안녕하세요^^
문제에 보면
둘로 나뉘는 두 부분집합은 서로소 집합(Disjoint Set)이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어야 합니다.
두 부분집합을 합하면 원래 입력으로 주어진 집합이 되어야 합니다.
아 그렇군요 감사합니다