美文网首页
递归与排列组合

递归与排列组合

作者: 内推er | 来源:发表于2017-07-05 22:57 被阅读0次

<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;
    }

相关文章

网友评论

      本文标题:递归与排列组合

      本文链接:https://www.haomeiwen.com/subject/uxdchxtx.html