How to analyse the time complexity of the recursive solution


  • 0
    D

    Found myself always confused about how to analyse the time complexity of recursive method like this one, can any one help me?

    This is my ac code:

    public class Solution {
      public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> rst = new ArrayList<List<Integer>>();
        List<Integer> prefix = new ArrayList<Integer>();
    
        rCombinationSum3(k, prefix, 1, n, rst);
    
        return rst;
      }
    
      public void rCombinationSum3(int k, List<Integer> prefix, int start, int target, List<List<Integer>> rst) {
        if(k == 0){
          if(sum(prefix) == target){
            rst.add(new ArrayList<Integer>(prefix));
          }
        }else{
          for(int i = start; i <= 9; i++){
            prefix.add(i);
            rCombinationSum3(k - 1, prefix, i + 1, target, rst);
            prefix.remove(prefix.size() - 1);
          }
        }
      }
    
      private int sum(List<Integer> list){
        int rst = 0;
    
        for(Integer n : list){
          rst += n;
        }
    
        return rst;
      }
    }

  • 1
    C

    I think in this case should be less than C(9, k), it means we need pick k numbers from 1 to 9. In a normal combination case, the complexity should be pow(2, n), where n is the number of elements we can choose from. Back to this question, the target sum is n, and we have backtracking process, so we don't need to generate the all C(9, k) subsets. Therefore the time complexity should be a value less than C(9, k), and has connection with the sum n.


Log in to reply
 

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