바둑이승차(DFS)

합이 같은 부분집합 문제와 별반 다를게 없다.

코드

function solution(c, arr){
        let n = arr.length, 
            answer = Number.MIN_SAFE_INTEGER;                   
        function DFS(L, sum) {
            if(sum>c) return;
            if(L === n) {
                answer=Math.max(answer, sum);
            }
            else {
                DFS(L+1,sum+arr[L])
                DFS(L+1,sum)
            }
        }
        DFS(0,0);
        return answer;
    }

 let arr=[81, 58, 42, 33, 61];
 console.log(solution(259, arr));

풀이

DFS를 이용하여 합의 경우를 다 구해보는 방법이다.
합(sum)이 제한중량(c)보다 클 경우는 재귀함수를 빠져 나오게 하고, 각 경우중 가장 큰 수를 구하는 방법이다.