LeetCode 77 Combinations(排列组合)

题目链接：https://leetcode.com/problems/combinations/#/description

Problem：给两个正数分别为n和k，求出从1，2.......n这n个数字选择k个数字作为一个组合，求出所有的组合。

数学问题：排列组合问题，可以得到这样的组合个数为：C（n,k）

代码实现：递归程序实现。

从1开始遍历到n为止，中间使用tempList保存每一个组合，只有当这个tempList的长度等于k时，将这个tempList添加到ans中。

因此该递归程序的出口为：保存暂时组合的数组长度等于k，

递归主要内容为向tempList中添加数字，调用自身，弹出tempList顶层的元素。

参考代码：

package leetcode_100;

import java.util.ArrayList;

import java.util.List;

public class Solution77 {

    public  List<List<Integer>> combine(int n, int k) {

        List<List<Integer>> ans = new ArrayList<List<Integer>>();

        match(ans,new ArrayList<Integer>(),1,n,k);

        return ans;

    }

    private  void match(List<List<Integer>> ans, ArrayList<Integer> arrayList, int start, int n, int k) {

        if(k==0){

            ans.add(new ArrayList<Integer>(arrayList));

            return;

        }

        for(int i = start ; i <= n ; i++){

            arrayList.add(i);

            match(ans,arrayList,i+1,n,k-1);

            arrayList.remove(arrayList.size()-1);

        }

    }

}

巴特西

LeetCode 77 Combinations(排列组合)

最新文章

热门文章