<p>216. Combination Sum III（https://leetcode.com/problems/combination-sum-iii/#/description）
这是leetcode第216题。因为自己是做到这个题目才思考这个问题。而这个题目是非重复排列组合，所以就从非重复排列组合的开始说起吧。
</p>
<p>排列组合有两种递归的方法，而区别重复和非重复，只需要做很小的一点代码改动就可以了。</p>

非重复排列组合

方法1：

<p>思想：对于第index个元素，依次查看后续每个元素index+i,尝试把他放入组合（尝试就是进行进一步递归）
</p>

List<List<Integer>> re=new ArrayList<List<Integer>>();
    public void combine(int index,int k,int n,List<Integer> temp){
        if(n<0) return;
        if(k==0&&n==0){
            re.add(new ArrayList<>(temp));
            return;
        }
        if(k<=0) return;
        for(int i=index;i<10;i++){
            temp.add(i);
            combine(i+1,k-1, n-i,temp);
            temp.remove(temp.size()-1);
        }
        return;
    }
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<Integer> temp=new ArrayList<>();
        combine(1,k, n, temp);
        return re;
    }

方法2：

<p>思想：对于第index个元素，只查看放入这个元素或者不放入这两种情况，然后递归后面一个元素index+1。</br>
注意此方法需要remove元素。</p>

List<List<Integer>> re=new ArrayList<List<Integer>>();
    public void combine(int index,int k,int n,List<Integer> temp){
        if(n<0) return;
        if(k==0&&n==0){
            re.add(new ArrayList<>(temp));
            return;
        }
        if(index>9) return;
        if(k<=0) return;
        temp.add(index);
        combine(index+1,k-1, n-index,temp);
        temp.remove(temp.size()-1);
        combine(index+1,k, n,temp);
        return;
    }
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<Integer> temp=new ArrayList<>();
        combine(1,k, n, temp);
        return re;
    }

有重复排列组合

其实对照前面的非重复排列组合，写出有重复的已经非常的简单了

方法1：

改动的地方：combine(i+1,k-1,n-i,temp)变成combine(i,k-1, n-i,temp)，因为第i个元素有可能重复被使用

List<List<Integer>> re=new ArrayList<List<Integer>>();
    public void combine(int index,int k,int n,List<Integer> temp){
        if(n<0) return;
        if(k==0&&n==0){
            re.add(new ArrayList<>(temp));
            return;
        }
        if(k<=0) return;
        for(int i=index;i<10;i++){
            temp.add(i);
            combine(i,k-1, n-i,temp);
            temp.remove(temp.size()-1);
        }
        return;
    }
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<Integer> temp=new ArrayList<>();
        combine(1,k, n, temp);
        return re;
    }

方法2：

改动的地方：combine(index+1,k-1, n-index,temp)变成combine(index,k-1, n-index,temp);因为第index个元素可能被重复使用

List<List<Integer>> re=new ArrayList<List<Integer>>();
    public void combine(int index,int k,int n,List<Integer> temp){
        if(n<0) return;
        if(k==0&&n==0){
            re.add(new ArrayList<>(temp));
            return;
        }
        if(index>9) return;
        if(k<=0) return;
        temp.add(index);
        combine(index,k-1, n-index,temp);
        temp.remove(temp.size()-1);
        combine(index+1,k, n,temp);
        return;
    }
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<Integer> temp=new ArrayList<>();
        combine(1,k, n, temp);
        return re;
    }