n๊ฐ์ ์์ด ์๋ ์ ์๊ฐ ์์ต๋๋ค. ์ด ์๋ฅผ ์ ์ ํ ๋ํ๊ฑฐ๋ ๋นผ์ ํ๊ฒ ๋๋ฒ๋ฅผ ๋ง๋ค๋ ค๊ณ ํฉ๋๋ค. ์๋ฅผ ๋ค์ด [1, 1, 1, 1, 1]๋ก ์ซ์ 3์ ๋ง๋ค๋ ค๋ฉด ๋ค์ ๋ค์ฏ ๋ฐฉ๋ฒ์ ์ธ ์ ์์ต๋๋ค.
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
์ฌ์ฉํ ์ ์๋ ์ซ์๊ฐ ๋ด๊ธด ๋ฐฐ์ด numbers, ํ๊ฒ ๋๋ฒ target์ด ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋ ์ซ์๋ฅผ ์ ์ ํ ๋ํ๊ณ ๋นผ์ ํ๊ฒ ๋๋ฒ๋ฅผ ๋ง๋๋ ๋ฐฉ๋ฒ์ ์๋ฅผ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์.
์ ํ์ฌํญ
์ฃผ์ด์ง๋ ์ซ์์ ๊ฐ์๋ 2๊ฐ ์ด์ 20๊ฐ ์ดํ์ ๋๋ค.
๊ฐ ์ซ์๋ 1 ์ด์ 50 ์ดํ์ธ ์์ฐ์์ ๋๋ค.
ํ๊ฒ ๋๋ฒ๋ 1 ์ด์ 1000 ์ดํ์ธ ์์ฐ์์ ๋๋ค.
๐ก DFS
๐ก ๋ ๊ฐ์ง ๊ฒฝ์ฐ๋ก ๋๋์ด์ numbers๋ฅผ ๋ํ ๋, ๋บ ๋ ๋ชจ๋ ๊ณ ๋ คํจ
๐ก numbers๋ฅผ ๋ชจ๋ ๋ค ์ฐ๊ณ target number๋ ์ผ์นํ ์์ count์ 1์ ๋ํด์ค
1) ๋ ๊ฐ์ง ๊ฒฝ์ฐ๋ก ๋๋์ด์ numbers๋ฅผ ๋ํ ๋, ๋บ ๋ ๋ชจ๋ ๊ณ ๋ คํจ
dfs(numbers, target, depth+1, ret+numbers[depth]);
dfs(numbers, target, depth+1, ret-numbers[depth]);
2) numbers๋ฅผ ๋ชจ๋ ๋ค ์ฐ๊ณ target number๋ ์ผ์นํ ์์ count์ 1์ ๋ํด์ค
if(depth == numbers.length){
if(ret == target)
count++;
return;
}
class Solution {
static int count = 0;
public int solution(int[] numbers, int target) {
int answer = 0;
dfs(numbers, target, 0, 0);
return answer = count;
}
public void dfs(int[] numbers, int target, int depth, int ret){
if(depth == numbers.length){
if(ret == target)
count++;
return;
} else {
dfs(numbers, target, depth+1, ret+numbers[depth]);
dfs(numbers, target, depth+1, ret-numbers[depth]);
}
}
}
์ฑ๊ณตโจ