Advertisement
Guest User

Untitled

a guest
Jul 19th, 2019
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.85 KB | None | 0 0
  1. const n = 4;
  2. const a = [1,2,4,7];
  3. const k = 13;
  4.  
  5. function main() {
  6. if(dfs(0,0)) console.log("Yes");
  7. else console.log("No");
  8.  
  9. // 全件探索で書いたらこう
  10. // let flag = false
  11. // for(let i = 0; i < n; i++) {
  12. // let sum = a[i];
  13. // for(let j = 1 ; j < n ; j++) {
  14. // sum += a[j];
  15. // if(sum === k){
  16. // flag=true;
  17. // break;
  18. // }
  19. // }
  20. // }
  21. // if(flag) {
  22. // console.log("Yes");
  23. // }else{
  24. // console.log("No");
  25. // }
  26. }
  27.  
  28. function dfs(i, sum) {
  29. if(i === n) return sum === k;     // n段目まで進んだら、sumがkと一致しているか判定
  30. if(dfs(i+1, sum)) return true;    //
  31. if(dfs(i+1, sum + a[i])) return true; //
  32.  
  33. return false
  34. }
  35.  
  36. console.time()
  37. main()
  38. console.timeEnd()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement