DP memorization, no need to compute unnecessary cells


  • 0
    V
    public List<List<Integer>> combine(int n, int k) {
            List<List<Integer>>[][] M = new List[n + 1][k + 1];
            for (int i = 0; i <= n; i++) {
                M[i][0] = new ArrayList<>();
                M[i][0].add(new ArrayList<>());
            }
            return dp(n, k, M);
        }
        
     public List<List<Integer>> dp(int n, int k, List<List<Integer>>[][] M) {
         if (M[n][k] == null) {
             M[n][k] = new ArrayList<>();
             List<List<Integer>> temp = dp(n - 1, k - 1, M);
             temp.forEach(l -> M[n][k].add(new ArrayList<>(l)));
             M[n][k].forEach(l -> l.add(n));
             if (n > k) {
                 M[n][k].addAll(dp(n - 1, k, M));
             }
         }
         return M[n][k];
     }
    

Log in to reply
 

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