Article From:https://www.cnblogs.com/MrSaver/p/9967654.html

LeetCode:Total Combination III [216]

Title Description

Find out the sum of all additions.OfCombination of numbersOnly positive integers containing 1-9 are allowed in combinations, and there are no duplicate numbers in each combination.

Explain:

  • All numbers are positive integers.
  • Unset cannot contain duplicate combinations.  

Example 1:

Input:k = 3, n = 7
Output: [[1,2,4]]

Example 2:

Input:k = 3, n = 9
Output: [[1,2,6], [1,3,5], [2,3,4]]

Title Analysis

  UseRecursive backtracking boxframeSolve problems.

JavaTitle Solution

class Solution {
      public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> ans =  new ArrayList<>();
        backtrack(ans,new ArrayList<>(),k,n,0,0,1);
        return ans;
    }

    public void backtrack(List<List<Integer>> list,List<Integer> tmpList,int k,int n,int curk,int curn,int num)
    {
        if(curn>n||curk>k)
            return;
        if(curk==k&&curn==n)
            list.add(new ArrayList<>(tmpList));
        else{
            for(int i=num;i<10;i++)
            {
                tmpList.add(i);
                backtrack(list,tmpList,k,n,curk+1,curn+i,i+1);
                tmpList.remove(tmpList.size()-1);
            }
        }
    }
}

 

Leave a Reply

Your email address will not be published. Required fields are marked *