Dynamic_Programming/bestSum.js at master · Beschuetzer/Dynamic_Programming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
//     //Optimization Problem
// //m = targetSum
// //n = numbers.length

// //Brute Force:
// //time: O(n^m * m) (* m comes from the remainderResult)
// //space: O(m^2)

// //Memoized:
// //time: O(m^2 * n)
// //space: O(m^2)

// //returns the shortest array of numbers adding up to targetSum (can return any one if there are ties)

// function bestSum (targetSum, numbers) {
//     if (targetSum === 0) return [];
//     if (targetSum < 0) return null;

//     let shortestResult = null;
//     for (let num of numbers) {
//         const remainder = targetSum - num;
//         const remainderResult = bestSum(remainder, numbers);
//         if (remainderResult !== null) {
//             remainderResult.push(num);
//             if (shortestResult === null || remainderResult.length < shortestResult.length) {
//                 shortestResult = remainderResult;
//             }
//         }
//     }
//     return shortestResult;
// }

// console.log(bestSum(7, [5,3,4,7]))  //[7]
// console.log(bestSum(7, [2,3,5]))  //[2,5]
// console.log(bestSum(8, [1,4,5]))  //[4,4];
// console.log(bestSum(8, [2,3,5]))  //[3,5];
// // console.log(bestSum(100, [1,2,5,25]))  //false;

// function bestSumMemo (targetSum, numbers, memo={}) {
//     if (targetSum === 0) return [];
//     if (targetSum < 0) return null;
//     if (targetSum in memo) return memo[targetSum];

//     let shortestResult = null;
//     for (let num of numbers) {
//         const remainder = targetSum - num;
//         const remainderResult = bestSumMemo(remainder, numbers, memo);
//         if (remainderResult !== null) {
//             // remainderResult.push(num);
//             const newArray = [...remainderResult, num];
//             if (shortestResult === null || newArray.length < shortestResult.length) {
//                 shortestResult = newArray;
//             }
//         }
//     }
//     memo[targetSum] = shortestResult;
//     return memo[targetSum];
// }

// console.log(bestSumMemo(7, [5,3,4,7]))  //[7]
// console.log(bestSumMemo(7, [2,3,5]))  //[2,5]
// console.log(bestSumMemo(8, [1,4,5]))  //[4,4];
// console.log(bestSumMemo(8, [2,3,5]))  //[3,5];
// console.log(bestSumMemo(100231, [1,2,5,25]))  //false;


function bestSumReview(targetSum, numArray, memo={}) {
    if (targetSum in memo) return memo[targetSum];
    if (targetSum === 0) return [];
    if (targetSum < 0) return null;

    let shortestResult = null;
    for(let num of numArray) {
        const remainder = targetSum - num;
        const remainderResult = bestSumReview(remainder, numArray, memo);
        if (remainderResult !== null) {
            //stuff to do
            const result = [...remainderResult, num];
            if (shortestResult === null || result.length < shortestResult.length) shortestResult = result;
        }
    }
    memo[targetSum] = shortestResult;
    return memo[targetSum];
}


console.log(bestSumReview(7, [5,3,4,7]))  //[7]
console.log(bestSumReview(7, [2,3,5]))  //[2,5]
console.log(bestSumReview(8, [1,4,5]))  //[4,4];
console.log(bestSumReview(8, [2,3,5]))  //[3,5];
console.log(bestSumReview(10000, [1,2,5,25]))  //false;