op로 분기점을 주고 싶었는데 감이 안 잡힌다..
function solution(numbers, target) {
let ch = Array.from({length:numbers.length}, () => 0);
let answer = 0;
let op = [true, false];
function Sum (L, sum) {
if (L>numbers.length) return;
if (sum>target) return;
if (sum<0) return;
if (L===numbers.length && sum===target) {
answer++;
}
else {
for (let i=0; i<numbers.length; i++) {
if (ch[i]==0) {
ch[i]=1;
for (let i=0; i<op.length; i++) {
if (op[i]==true) {
Sum(L+1, sum+numbers[i]);
ch[i]=0;
}
else {
Sum(L+1, sum-numbers[i]);
ch[i]=0;
}
}
}
}
}
}
Sum(0, 0);
return answer;
}
console.log(solution([1, 1, 1, 1, 1], 3))
성능 고려하지 않고 ans에 배열들을 전부 넣어서 new Set으로 중복을 제거하고 풀려고 했더니 문제점을 발견했다.
단순히 op로 분기점을 나누니까 numbers를 전부 넣는 게 아니라 2개만 넣어도 -+로 나눠서 4개가 계산된다는 점이 문제였다.
2차원 배열에서 중복 제거하는 법
[...new Set(ans.join('|').split('|'))].map(v => v.split(',')).map(v => v.map(a => +a));
function solution(numbers, target) {
let ch = Array.from({length:numbers.length}, () => 0);
let answer = 0;
let op = [true, false];
let tmp = [];
let ans = [];
function Sum (L) {
if (L==numbers.length) {
// console.log(tmp)
ans.push(tmp.slice());
}
else {
for (let i=0; i<numbers.length; i++) {
if (ch[i]==0) {
ch[i]=1;
for (let i=0; i<op.length; i++) {
if (op[i]==true) {
tmp[L] = -numbers[i];
Sum(L+1);
ch[i]=0;
}
else {
tmp[L] = +numbers[i];
Sum(L+1);
ch[i]=0;
}
}
}
}
}
}
Sum(0);
console.log(ans);
ans = [...new Set(ans.join('|').split('|'))].map(v => v.split(',')).map(v => v.map(a => +a));
for (let i=0; i<ans.length; i++) {
let sum = ans[i].reduce((a,b) => a+b);
if (sum === target) answer++;
}
return answer;
}
console.log(solution([4, 1, 2, 1], 4))
재귀 내 for문을 numbers로 도는 게 아니라 op로 순회할 수 있게 변경했다.
그리고 각 numbers의 자리를 고정하기 위해
tmp[L] = +-numbers[i];
를 사용했다.
배열을 썼으므로 성능이 좋지 않다.
function solution(numbers, target) {
let answer = 0;
let op = [true, false];
let tmp = [];
function Sum (L) {
if (L==numbers.length) {
// console.log(tmp.slice())
let sum = tmp.reduce((a,b) => a+b);
if (sum === target) answer++;
}
else {
for (let i=0; i<op.length; i++) {
if (op[i]==true) {
tmp[L] = +numbers[L];
Sum(L+1);
}
else {
tmp[L] = -numbers[L];
Sum(L+1);
}
}
}
}
Sum(0);
return answer;
}
console.log(solution([4, 1, 2, 1], 4))
아래 풀이 역시 분기점을 +냐 -냐 2개로 잡아서 푼 풀이다.
function solution(numbers, target) {
let answer = 0;
getAnswer(0,0);
function getAnswer(x,value) {
if(x<numbers.length){
getAnswer(x+1,value + numbers[x]);
getAnswer(x+1,value - numbers[x]);
} else{
if(value === target){
answer++
}
}
}
return answer;
}
console.log(solution([4, 1, 2, 1], 4))