java - 使用递归的组合 VS 排列

Question

最近在练习算法题。我发现了两个非常相似的问题并将它们放在一起以供学习。

Question 1: Have all the k combinations from n - e.g. n=4 and k=3 then we return {[1,2,3],[1,3,4],[2,3,4],[1,2,4]}

回答:

public static List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    if(k > n || n <= 0) {
        return res;
    }
    ArrayList<Integer> a = new ArrayList<Integer>();
    helper(res, n, k, 1, a);
    return res;
}

private static void helper(List<List<Integer>> res, int n, int k, int start, ArrayList<Integer> a) {
    if(a.size() == k){
        res.add(new ArrayList<Integer>(a));
        return;
    }

    for(int i=start; i<=n; i++) {
        a.add(i);
        helper(res, n, k, i+1, a);
        a.remove(a.size()-1);
    }
}

Question 2: Have all the permutations of an array: {1,2,3} -> {123},{132},{213},{231},{321},{312}.

回答:

public static List<List<Integer>> permute(int[] num) {
    List<List<Integer>> rst = new ArrayList<List<Integer>>();
    if (num == null || num.length == 0) {
        return rst; 
    }

    ArrayList<Integer> list = new ArrayList<Integer>();
    helper(rst, list, num);
    return rst;
}

public static void helper(List<List<Integer>> rst, ArrayList<Integer> list, int[] num){
    if(list.size() == num.length) {
        rst.add(new ArrayList<Integer>(list));
        return;
    }

    for(int i = 0; i<num.length; i++) {
        if(list.contains(num[i])){
            continue;
        }
        list.add(num[i]);
        helper(rst, list, num);
        list.remove(list.size() - 1);
    }
}

对于问题2，我们从索引0开始；对于问题1，为什么for循环索引需要从start开始，为什么我们需要给helper方法传递一个start参数？

Answer 1

在查看 Prolog 代码时不要感到惊讶。我认为这有助于从不同的角度看待问题。

组合是包含给定数量元素的集合的任意子集。元素的顺序无关紧要。

comb(0,_,[]).
comb(N,[X|T],[X|Comb]):-N>0,N1 is N-1,comb(N1,T,Comb).
comb(N,[_|T],Comb):-N>0,comb(N,T,Comb).

列表 L 的排列是一个列表，其中包含列表 L 的所有元素，并按某种顺序排列。

perm(List,[H|Perm]):-select(H,List,Rest),perm(Rest,Perm).
perm([],[]).

select(X,[X|T],T).
select(X,[H|T],[H|NT]):-select(X,T,NT).

所以我的答案是:

我们需要组合情况下的起始索引来指定子集大小。