MENU

LeetCode77. 组合

July 11, 2018 • Read: 2382 • LeetCode阅读设置

class Solution {
    public static List<List<Integer>> ans = new ArrayList<List<Integer>>();
    public static int[] path = new int[100];
    public static int K;
    public static void dfs(int idx,int n,int k) {//idx [0,n)
        if(k == 0) {
            List<Integer> tmp = new ArrayList<Integer>();
            for(int i = 0;i < K;i++) {
                tmp.add(path[i]);
            }
            ans.add(tmp);
            return;
        }
        for(int i = idx + 1;i <= n;i++) {
            path[k - 1] = i;
            dfs(i, n, k - 1);
        }
    }
    public List<List<Integer>> combine(int n, int k) {
        ans.clear();
        K = k;
        dfs(0,n,k);
        return ans;
    }
}

常规dfs题,首先在dfs函数中判断边界条件,因为只要取到k个数就够了,所以边界条件当k用完,也就是k==0就应该return了。然后再看dfs函数内部的实现,肯定是个for循环无疑了,但是这个for循环初始值应该是多少,这就要追溯到idx的值表示什么含义了。idx值在这里表示的含义是取到的第n个数是多少,看样例[2,4],就是当已经取到2之后,后面的数就是第k个数,应该取什么,所以for循环的初值i至少应该是idx+1,只少要比idx大,不然就会产生[0,0],[1,1],这样的结果,而i最大也不能超过n,所以i<=n

Last Modified: May 12, 2021
Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment