45_subsetSum

45_subsetSum

이건 무조건 더 효율적인 방법이 있을 것 같다

무조건 시간초과같은거 날것같았는데 안나서 신기했다

 

const subsetSum = function (set, bound) {
  let res=0;
  let ans=0;
  set.sort((a,b)=>b-a); //역순정렬함. [15, 8, 3, 1]
  for(let i=0;i<set.length;i++) { 
    res = set[i]; //일단 res에 i번쨰 값을 넣어준다
    for(let j=i+1;j<set.length;j++) { //i번째 수 다음것부터 배열끝까지
      if(res+set[j]<=bound) { //만약에 계속 더하고있는 res와 j번째 수의 합이 bound보다 작거나 같으면
        res = res+set[j];// res에 더해준다
      }
    }
    //현재 ans에는 bound보다 작거나 같은 수 중에 가장 bound에 가까운 합의 값이 들어가있다 
    if(res>ans && res<=bound) ans = res; //따라서 ans값이 바뀌려면 ans보다는 커야하고 res보다는 작거나 같아야한다
  }
  return ans;
};