Why cache is not used for this problem?


  • 0
    D

    This is my code:

    import java.util.*;
    
    public class CombinationSumIII {
      //k nums, target: n
      public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> rst = new ArrayList<List<Integer>>();
        List<Integer> prefix = new ArrayList<Integer>();
    
        rCombSum3(k, n, prefix, rst);
    
        return rst;
      }
    
      private void rCombSum3(int k, int n, List<Integer> prefix, List<List<Integer>> rst){
        if(k == 0 && n == 0){
          rst.add(new ArrayList<Integer>(prefix));
          return;
        }else if(k == 0 || n <= 0){
          return;
        }
    
        int start = prefix.size() == 0? 1 : prefix.get(prefix.size() - 1) + 1;
    
        for(int i = start; i <= 9; i++){
          prefix.add(i);
          rCombSum3(k - 1, n - i, prefix, rst);
          prefix.remove(prefix.size() - 1);
        }
      }
    }
    

    This recursive solution is really familiar for me, that I thought a cache should be used to speed up this recursive solution(to avoid duplicate computation), but turned out it is ok to get accepted without cache, is this one any different from other ones?


Log in to reply
 

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