Find all valid combinations of k numbers that sum up to n such that the following conditions are true:


	Only numbers 1 through 9 are used.
	Each number is used at most once.


Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

&nbsp;
Example 1:

Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation:
1 + 2 + 4 = 7
There are no other valid combinations.

Example 2:

Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.


Example 3:

Input: k = 4, n = 1
Output: []
Explanation: There are no valid combinations.
Using 4 different numbers in the range [1,9], the smallest sum we can get is 1+2+3+4 = 10 and since 10 &gt; 1, there are no valid combination.


&nbsp;
Constraints:


	2 &lt;= k &lt;= 9
	1 &lt;= n &lt;= 60


class Solution:
    
    def solve(self,k,target,ans,temp,idx,nums):
        
        if idx==len(nums):
            if target==0 and k==0:
                ans.append(list(temp))
            return
        
        if nums[idx]<=target:
            
            temp.append(nums[idx])
            self.solve(k-1,target-nums[idx],ans,temp,idx+1,nums)
            temp.pop()
        
        self.solve(k,target,ans,temp,idx+1,nums)
        

    
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        
        ans = []
        temp = []
        idx = 0
        nums = list(range(1,10))
        
        self.solve(k,n,ans,temp,idx,nums)
        return ans
                
//Recursion

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        //int[] arr = new int{1,2,3,4,5,6,7,8,9};
        List<Integer> ds = new ArrayList<>();
        helper(1, n, k, ds, ans);
        return ans;
    }
    private static void helper(int i, int tar, int k, List<Integer> ds, List<List<Integer>> ans){
        //base
        if(k == 0) {
            if(tar == 0){
                ans.add(new ArrayList<>(ds));
            }
            return;
        }
        if(tar == 0) return; //bcz if k is not zero and tar is zero then no possible valid combination
        if(i > tar) return;
        if(i > 9) return;

        //Take
        if(i <= tar) {
            ds.add(i);
            helper(i+1, tar - i, k-1 , ds, ans);
            ds.remove(ds.size()-1);
        }
        // Not take
        helper(i+1 , tar, k , ds, ans);

        return;
    }
}
class Solution {
public:
    vector<vector<int>> ans;
    //declare temp global vector in this vector we will store temprary combinations
    vector<int> temp;
    void solve(int k,int n,int order){
        //check if our target became zero and combination size became zero then push temp vector inside the ans it means this temp vector combination having sum is equal to target and size of vector is equal to k
        if(n==0 && k==0){
            ans.push_back(temp);
            return;
        }
        //check if our target is less than zero then return 
        if(n<0) return;
         // take for loop and check for all posibility ahead of order
        for(int i=order;i<=9;i++){
            //push current index value
            temp.push_back(i);
            // call solve function for further posiblity
            solve(k-1,n-i,i+1);
            //Pop last push value 
            temp.pop_back();
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        solve(k,n,1);
        return ans;
    }
};
/**
 * @param {number} k
 * @param {number} n
 * @return {number[][]}
 */
var combinationSum3 = function(k, n) {
    const ans = [];
    const st = [];

    function dfs(start, t) {
        if (t === 0 && st.length === k) {
            ans.push(Array.from(st));
            return;
        }
        for (let i = start; i <= 9 && st.length < k; i++) {
            if (i > t) break;
            st.push(i);
            dfs(i + 1, t - i);
            st.pop();
        }
    }

    dfs(1, n);

    return ans;
};
Combination Sum III