LeetCode216. 组合总和 III

简单的dfs问题，标记每一个数用没用过，没用过就用，v[i]=true,k--,n-=i，然后回溯就只需要将他们还原就行，注意这里是不能重复选,因此下一次选择的应该比这次要大，所以循环每次的初值是i=idx+1

class Solution {
    public List<List<Integer>> ans = new ArrayList<List<Integer>>();
    public boolean[] v = new boolean[11];
    public void dfs(int idx,int k,int n) {
        if(n < 0 || idx > 9 || k < 0)
            return;
        if(n == 0 && k == 0) {
            List<Integer> tmp = new ArrayList<Integer>();
            for(int i = 1;i < 10;i++) 
                if(v[i])
                    tmp.add(i);
            ans.add(tmp);
        }
        for(int i = idx + 1;i < 10;i++) {
            if(!v[i]) {
                v[i] = true;
                --k;
                n -= i;
                dfs(i,k,n);
                v[i] = false;
                ++k;
                n += i;
            }
        }
    }
    public List<List<Integer>> combinationSum3(int k, int n) {
        ans.clear();
        dfs(0,k,n);
        return ans;
    }
}