Combinations v.s Combination Sum III (Java)


  • 1
    I

    These two questions are very similar, so here I am going to put these two questions into comparisons.

    In Combinations, given k is the length of the sub-list, n is the last number of combination, return all possible combinations of k numbers out of 1 ... n.

    In Combination Sum III, k is the length of the sub-list, n is the target sum, return all possible combinations of k numbers that add up to n. Here, we limit the number used from 1 to 9.

    What's the similarities?

    1. Both start at 1
    2. Combinations ends ranges from n - k + 1 to n , Combination Sum III from 1 to 9
    3. Combinations adds sub-list when sub-list size is equal to k, Combination Sum III adds sub-list when sub-list size is equal to k and remaining equals 0 (subtract i from n in loop)

    Combinations :

    public List<List<Integer>> combine(int n, int k) {
       List<List<Integer>> list = new ArrayList<>();
       backtrack(list, new ArrayList<Integer>(), k, 1, n - k + 1);
       return list;
    }
    
    private void backtrack(List<List<Integer>> list, List<Integer> tempList, int k, int start, int end) {
       if (tempList.size() == k) list.add(new ArrayList<>(tempList)); 
       else{
          for (int i = start; i <= end; i++) {
             tempList.add(i);
             backtrack(list, tempList, k, i + 1, end + 1);
             tempList.remove(tempList.size() - 1);
          }
       }
    }
    

    Combination Sum III :

    public List<List<Integer>> combinationSum3(int k, int n) {
       List<List<Integer>> list = new ArrayList<>();
       backtrack(list, new ArrayList<Integer>(), k, n, 1);
       return list;
    }
    
    private void backtrack(List<List<Integer>> list, List<Integer> tempList, int k, int remain, int start) {
       if(tempList.size() == k && remain == 0) list.add(new ArrayList<>(tempList));
       else{
          for(int i = start; i <= 9; i++) {
             tempList.add(i);
             backtrack(list, tempList, k, remain - i, i + 1);
             tempList.remove(tempList.size() - 1);
          }
       } 
    }

  • 0
    A

    @issac3 Thanks for detailed analysis. but why does Combination range start from n - k + 1? This is the only part that eludes me. Can you please help withe the reasoning behind this? Thanks.


Log in to reply
 

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