Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- const n = 4;
- const a = [1,2,4,7];
- const k = 13;
- function main() {
- if(dfs(0,0)) console.log("Yes");
- else console.log("No");
- // 全件探索で書いたらこう
- // let flag = false
- // for(let i = 0; i < n; i++) {
- // let sum = a[i];
- // for(let j = 1 ; j < n ; j++) {
- // sum += a[j];
- // if(sum === k){
- // flag=true;
- // break;
- // }
- // }
- // }
- // if(flag) {
- // console.log("Yes");
- // }else{
- // console.log("No");
- // }
- }
- function dfs(i, sum) {
- if(i === n) return sum === k; // n段目まで進んだら、sumがkと一致しているか判定
- if(dfs(i+1, sum)) return true; //
- if(dfs(i+1, sum + a[i])) return true; //
- return false
- }
- console.time()
- main()
- console.timeEnd()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement