这里是leetcode问题,用于组合和问题。
有一个答案是java(或见下文)

public class Solution {
    public List<List<Integer>> combinationSum(int[] cands, int t) {
        Arrays.sort(cands); // sort candidates to try them in asc order
        List<List<List<Integer>>> dp = new ArrayList<>();
        for (int i = 1; i <= t; i++) { // run through all targets from 1 to t
            List<List<Integer>> newList = new ArrayList(); // combs for curr i
            // run through all candidates <= i
            for (int j = 0; j < cands.length && cands[j] <= i; j++) {
                // special case when curr target is equal to curr candidate
                if (i == cands[j]) newList.add(Arrays.asList(cands[j]));
                // if current candidate is less than the target use prev results
                else for (List<Integer> l : dp.get(i-cands[j]-1)) {
                    if (cands[j] <= l.get(0)) {
                        List cl = new ArrayList<>();
                        cl.add(cands[j]); cl.addAll(l);
                        newList.add(cl);
                    }
                }
            }
            dp.add(newList);
        }
        return dp.get(t-1);
    }
}

我需要用javascript转换它。
这是我的尝试。
function sortFunc(a, b) {
    return a-b;
}

function combinationSum(cands, t) {
    cands.sort(sortFunc);

    let dp = []; //[[[]]];

    for (let i = 1; i <= t; i++) {

        console.log('-- i --');
        console.log(i);

        let newList = []; // [[]];

        for (let j = 0; j < cands.length && cands[j] <= i; j++)
        {
            console.log('-- j --');
            console.log(j);

            if (i === cands[j]) {

                console.log('-- push --');
                console.log(i);

                newList.push([cands[j]]);
            }
            else {
                // list of int
                let myListList = dp[i-cands[j]-1];

                for(let k=0; k<myListList.length; k++) {
                    let myList = myListList;

                    if(cands[j] <= myList[0]) {
                        myListList.unshift([cands[j]]);
                        newList.push(myListList);
                    }
                }
            }
        }

        dp.push(newList);
    }

    return dp[t-1];
}

let arr = [2, 3, 5];
let t = 15;
let out = combinationSum(arr, t);
console.log(out);

我对代码有些了解,但不是很多目前,我的javascript处于无限循环中。
有人知道为什么吗?
或者你对“组合和”有更好的解决方案?

最佳答案

在最后一个for循环中,您偏离了轨道,并根据循环的长度不断添加到循环中的myNewList,这样循环就不会结束。
这是一个非常接近原版的版本:

function sortFunc(a, b) {
  return a - b;
}

function combinationSum(cands, t) {
  cands.sort(sortFunc);

  let dp = []; //[[[]]];

  for (let i = 1; i <= t; i++) {
    let newList = []; // [[]];

    for (let j = 0; j < cands.length && cands[j] <= i; j++) {
      if (i === cands[j]) {
        newList.push([cands[j]]);
      } else {
        for (l of dp[i - cands[j] - 1]) {  // for of is similar to `for (List<Integer> l : dp.get(i-cands[j]-1))`
          if (cands[j] <= l[0]) {
            let cl = [cands[j], ...l]     // use spread ...l to get ArrayList.addall() behavior
            newList.push(cl)
          }
        }
      }
    }
    dp.push(newList);
  }

  return dp[t - 1];
}

let arr = [2, 3, 5, 4];
let t = 7;
let out = combinationSum(arr, t);
console.log(out);

09-25 19:08