Javascript one liner, faster than 99%


  • 0
    M
    var combinationSum3 = function(k, n) {
        return ([{"0":[[]]},{"1":[[1]]},{"1":[[2]]},{"1":[[3]],"2":[[1,2]]},{"1":[[4]],"2":[[1,3]]},{"1":[[5]],"2":[[1,4],[2,3]]},{"1":[[6]],"2":[[1,5],[2,4]],"3":[[1,2,3]]},{"1":[[7]],"2":[[1,6],[2,5],[3,4]],"3":[[1,2,4]]},{"1":[[8]],"2":[[1,7],[2,6],[3,5]],"3":[[1,2,5],[1,3,4]]},{"1":[[9]],"2":[[1,8],[2,7],[3,6],[4,5]],"3":[[1,2,6],[1,3,5],[2,3,4]]},{"2":[[1,9],[2,8],[3,7],[4,6]],"3":[[1,2,7],[1,3,6],[1,4,5],[2,3,5]],"4":[[1,2,3,4]]},{"2":[[2,9],[3,8],[4,7],[5,6]],"3":[[1,2,8],[1,3,7],[1,4,6],[2,3,6],[2,4,5]],"4":[[1,2,3,5]]},{"2":[[3,9],[4,8],[5,7]],"3":[[1,2,9],[1,3,8],[1,4,7],[1,5,6],[2,3,7],[2,4,6],[3,4,5]],"4":[[1,2,3,6],[1,2,4,5]]},{"2":[[4,9],[5,8],[6,7]],"3":[[1,3,9],[1,4,8],[1,5,7],[2,3,8],[2,4,7],[2,5,6],[3,4,6]],"4":[[1,2,3,7],[1,2,4,6],[1,3,4,5]]},{"2":[[5,9],[6,8]],"3":[[1,4,9],[1,5,8],[1,6,7],[2,3,9],[2,4,8],[2,5,7],[3,4,7],[3,5,6]],"4":[[1,2,3,8],[1,2,4,7],[1,2,5,6],[1,3,4,6],[2,3,4,5]]},{"2":[[6,9],[7,8]],"3":[[1,5,9],[1,6,8],[2,4,9],[2,5,8],[2,6,7],[3,4,8],[3,5,7],[4,5,6]],"4":[[1,2,3,9],[1,2,4,8],[1,2,5,7],[1,3,4,7],[1,3,5,6],[2,3,4,6]],"5":[[1,2,3,4,5]]},{"2":[[7,9]],"3":[[1,6,9],[1,7,8],[2,5,9],[2,6,8],[3,4,9],[3,5,8],[3,6,7],[4,5,7]],"4":[[1,2,4,9],[1,2,5,8],[1,2,6,7],[1,3,4,8],[1,3,5,7],[1,4,5,6],[2,3,4,7],[2,3,5,6]],"5":[[1,2,3,4,6]]},{"2":[[8,9]],"3":[[1,7,9],[2,6,9],[2,7,8],[3,5,9],[3,6,8],[4,5,8],[4,6,7]],"4":[[1,2,5,9],[1,2,6,8],[1,3,4,9],[1,3,5,8],[1,3,6,7],[1,4,5,7],[2,3,4,8],[2,3,5,7],[2,4,5,6]],"5":[[1,2,3,4,7],[1,2,3,5,6]]},{"3":[[1,8,9],[2,7,9],[3,6,9],[3,7,8],[4,5,9],[4,6,8],[5,6,7]],"4":[[1,2,6,9],[1,2,7,8],[1,3,5,9],[1,3,6,8],[1,4,5,8],[1,4,6,7],[2,3,4,9],[2,3,5,8],[2,3,6,7],[2,4,5,7],[3,4,5,6]],"5":[[1,2,3,4,8],[1,2,3,5,7],[1,2,4,5,6]]},{"3":[[2,8,9],[3,7,9],[4,6,9],[4,7,8],[5,6,8]],"4":[[1,2,7,9],[1,3,6,9],[1,3,7,8],[1,4,5,9],[1,4,6,8],[1,5,6,7],[2,3,5,9],[2,3,6,8],[2,4,5,8],[2,4,6,7],[3,4,5,7]],"5":[[1,2,3,4,9],[1,2,3,5,8],[1,2,3,6,7],[1,2,4,5,7],[1,3,4,5,6]]},{"3":[[3,8,9],[4,7,9],[5,6,9],[5,7,8]],"4":[[1,2,8,9],[1,3,7,9],[1,4,6,9],[1,4,7,8],[1,5,6,8],[2,3,6,9],[2,3,7,8],[2,4,5,9],[2,4,6,8],[2,5,6,7],[3,4,5,8],[3,4,6,7]],"5":[[1,2,3,5,9],[1,2,3,6,8],[1,2,4,5,8],[1,2,4,6,7],[1,3,4,5,7],[2,3,4,5,6]]},{"3":[[4,8,9],[5,7,9],[6,7,8]],"4":[[1,3,8,9],[1,4,7,9],[1,5,6,9],[1,5,7,8],[2,3,7,9],[2,4,6,9],[2,4,7,8],[2,5,6,8],[3,4,5,9],[3,4,6,8],[3,5,6,7]],"5":[[1,2,3,6,9],[1,2,3,7,8],[1,2,4,5,9],[1,2,4,6,8],[1,2,5,6,7],[1,3,4,5,8],[1,3,4,6,7],[2,3,4,5,7]],"6":[[1,2,3,4,5,6]]},{"3":[[5,8,9],[6,7,9]],"4":[[1,4,8,9],[1,5,7,9],[1,6,7,8],[2,3,8,9],[2,4,7,9],[2,5,6,9],[2,5,7,8],[3,4,6,9],[3,4,7,8],[3,5,6,8],[4,5,6,7]],"5":[[1,2,3,7,9],[1,2,4,6,9],[1,2,4,7,8],[1,2,5,6,8],[1,3,4,5,9],[1,3,4,6,8],[1,3,5,6,7],[2,3,4,5,8],[2,3,4,6,7]],"6":[[1,2,3,4,5,7]]},{"3":[[6,8,9]],"4":[[1,5,8,9],[1,6,7,9],[2,4,8,9],[2,5,7,9],[2,6,7,8],[3,4,7,9],[3,5,6,9],[3,5,7,8],[4,5,6,8]],"5":[[1,2,3,8,9],[1,2,4,7,9],[1,2,5,6,9],[1,2,5,7,8],[1,3,4,6,9],[1,3,4,7,8],[1,3,5,6,8],[1,4,5,6,7],[2,3,4,5,9],[2,3,4,6,8],[2,3,5,6,7]],"6":[[1,2,3,4,5,8],[1,2,3,4,6,7]]},{"3":[[7,8,9]],"4":[[1,6,8,9],[2,5,8,9],[2,6,7,9],[3,4,8,9],[3,5,7,9],[3,6,7,8],[4,5,6,9],[4,5,7,8]],"5":[[1,2,4,8,9],[1,2,5,7,9],[1,2,6,7,8],[1,3,4,7,9],[1,3,5,6,9],[1,3,5,7,8],[1,4,5,6,8],[2,3,4,6,9],[2,3,4,7,8],[2,3,5,6,8],[2,4,5,6,7]],"6":[[1,2,3,4,5,9],[1,2,3,4,6,8],[1,2,3,5,6,7]]},{"4":[[1,7,8,9],[2,6,8,9],[3,5,8,9],[3,6,7,9],[4,5,7,9],[4,6,7,8]],"5":[[1,2,5,8,9],[1,2,6,7,9],[1,3,4,8,9],[1,3,5,7,9],[1,3,6,7,8],[1,4,5,6,9],[1,4,5,7,8],[2,3,4,7,9],[2,3,5,6,9],[2,3,5,7,8],[2,4,5,6,8],[3,4,5,6,7]],"6":[[1,2,3,4,6,9],[1,2,3,4,7,8],[1,2,3,5,6,8],[1,2,4,5,6,7]]},{"4":[[2,7,8,9],[3,6,8,9],[4,5,8,9],[4,6,7,9],[5,6,7,8]],"5":[[1,2,6,8,9],[1,3,5,8,9],[1,3,6,7,9],[1,4,5,7,9],[1,4,6,7,8],[2,3,4,8,9],[2,3,5,7,9],[2,3,6,7,8],[2,4,5,6,9],[2,4,5,7,8],[3,4,5,6,8]],"6":[[1,2,3,4,7,9],[1,2,3,5,6,9],[1,2,3,5,7,8],[1,2,4,5,6,8],[1,3,4,5,6,7]]},{"4":[[3,7,8,9],[4,6,8,9],[5,6,7,9]],"5":[[1,2,7,8,9],[1,3,6,8,9],[1,4,5,8,9],[1,4,6,7,9],[1,5,6,7,8],[2,3,5,8,9],[2,3,6,7,9],[2,4,5,7,9],[2,4,6,7,8],[3,4,5,6,9],[3,4,5,7,8]],"6":[[1,2,3,4,8,9],[1,2,3,5,7,9],[1,2,3,6,7,8],[1,2,4,5,6,9],[1,2,4,5,7,8],[1,3,4,5,6,8],[2,3,4,5,6,7]]},{"4":[[4,7,8,9],[5,6,8,9]],"5":[[1,3,7,8,9],[1,4,6,8,9],[1,5,6,7,9],[2,3,6,8,9],[2,4,5,8,9],[2,4,6,7,9],[2,5,6,7,8],[3,4,5,7,9],[3,4,6,7,8]],"6":[[1,2,3,5,8,9],[1,2,3,6,7,9],[1,2,4,5,7,9],[1,2,4,6,7,8],[1,3,4,5,6,9],[1,3,4,5,7,8],[2,3,4,5,6,8]],"7":[[1,2,3,4,5,6,7]]},{"4":[[5,7,8,9]],"5":[[1,4,7,8,9],[1,5,6,8,9],[2,3,7,8,9],[2,4,6,8,9],[2,5,6,7,9],[3,4,5,8,9],[3,4,6,7,9],[3,5,6,7,8]],"6":[[1,2,3,6,8,9],[1,2,4,5,8,9],[1,2,4,6,7,9],[1,2,5,6,7,8],[1,3,4,5,7,9],[1,3,4,6,7,8],[2,3,4,5,6,9],[2,3,4,5,7,8]],"7":[[1,2,3,4,5,6,8]]},{"4":[[6,7,8,9]],"5":[[1,5,7,8,9],[2,4,7,8,9],[2,5,6,8,9],[3,4,6,8,9],[3,5,6,7,9],[4,5,6,7,8]],"6":[[1,2,3,7,8,9],[1,2,4,6,8,9],[1,2,5,6,7,9],[1,3,4,5,8,9],[1,3,4,6,7,9],[1,3,5,6,7,8],[2,3,4,5,7,9],[2,3,4,6,7,8]],"7":[[1,2,3,4,5,6,9],[1,2,3,4,5,7,8]]},{"5":[[1,6,7,8,9],[2,5,7,8,9],[3,4,7,8,9],[3,5,6,8,9],[4,5,6,7,9]],"6":[[1,2,4,7,8,9],[1,2,5,6,8,9],[1,3,4,6,8,9],[1,3,5,6,7,9],[1,4,5,6,7,8],[2,3,4,5,8,9],[2,3,4,6,7,9],[2,3,5,6,7,8]],"7":[[1,2,3,4,5,7,9],[1,2,3,4,6,7,8]]},{"5":[[2,6,7,8,9],[3,5,7,8,9],[4,5,6,8,9]],"6":[[1,2,5,7,8,9],[1,3,4,7,8,9],[1,3,5,6,8,9],[1,4,5,6,7,9],[2,3,4,6,8,9],[2,3,5,6,7,9],[2,4,5,6,7,8]],"7":[[1,2,3,4,5,8,9],[1,2,3,4,6,7,9],[1,2,3,5,6,7,8]]},{"5":[[3,6,7,8,9],[4,5,7,8,9]],"6":[[1,2,6,7,8,9],[1,3,5,7,8,9],[1,4,5,6,8,9],[2,3,4,7,8,9],[2,3,5,6,8,9],[2,4,5,6,7,9],[3,4,5,6,7,8]],"7":[[1,2,3,4,6,8,9],[1,2,3,5,6,7,9],[1,2,4,5,6,7,8]]},{"5":[[4,6,7,8,9]],"6":[[1,3,6,7,8,9],[1,4,5,7,8,9],[2,3,5,7,8,9],[2,4,5,6,8,9],[3,4,5,6,7,9]],"7":[[1,2,3,4,7,8,9],[1,2,3,5,6,8,9],[1,2,4,5,6,7,9],[1,3,4,5,6,7,8]]},{"5":[[5,6,7,8,9]],"6":[[1,4,6,7,8,9],[2,3,6,7,8,9],[2,4,5,7,8,9],[3,4,5,6,8,9]],"7":[[1,2,3,5,7,8,9],[1,2,4,5,6,8,9],[1,3,4,5,6,7,9],[2,3,4,5,6,7,8]]},{"6":[[1,5,6,7,8,9],[2,4,6,7,8,9],[3,4,5,7,8,9]],"7":[[1,2,3,6,7,8,9],[1,2,4,5,7,8,9],[1,3,4,5,6,8,9],[2,3,4,5,6,7,9]],"8":[[1,2,3,4,5,6,7,8]]},{"6":[[2,5,6,7,8,9],[3,4,6,7,8,9]],"7":[[1,2,4,6,7,8,9],[1,3,4,5,7,8,9],[2,3,4,5,6,8,9]],"8":[[1,2,3,4,5,6,7,9]]},{"6":[[3,5,6,7,8,9]],"7":[[1,2,5,6,7,8,9],[1,3,4,6,7,8,9],[2,3,4,5,7,8,9]],"8":[[1,2,3,4,5,6,8,9]]},{"6":[[4,5,6,7,8,9]],"7":[[1,3,5,6,7,8,9],[2,3,4,6,7,8,9]],"8":[[1,2,3,4,5,7,8,9]]},{"7":[[1,4,5,6,7,8,9],[2,3,5,6,7,8,9]],"8":[[1,2,3,4,6,7,8,9]]},{"7":[[2,4,5,6,7,8,9]],"8":[[1,2,3,5,6,7,8,9]]},{"7":[[3,4,5,6,7,8,9]],"8":[[1,2,4,5,6,7,8,9]]},{"8":[[1,3,4,5,6,7,8,9]]},{"8":[[2,3,4,5,6,7,8,9]]},{"9":[[1,2,3,4,5,6,7,8,9]]}][n] || [])[k] || []
    };
    

    To generate the above monstrosity, I used the following:

    (() => {
      const sums = Array.from({length: 46}, _ => [])
    
      for (let i=0; i<(1<<9); i++) {
        let sum = 0
        const arr = []
        for (let j=0; j<9; j++) {
          if ((i & (1<<j)) != 0) {
            sum += (j+1)
            arr.push(j+1)
          }
        }
        sums[sum].push(arr)
      }
      for (let i=0; i<sums.length; i++) {
        const map = new Map()
        sums[i].sort().forEach(s => {
          map.set(s.length, (map.get(s.length) || []).concat([s]))
        })
        sums[i] = {}
        map.forEach((v,k) => { sums[i][k] = v })
      }
      return JSON.stringify(sums)
    })()
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.