2
votes

I'm practicing algorithm questions recently. I found two very similar questions and put them together for learning purposes.

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

Answer:

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

Answer:

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

For question 2, we start from index 0; for question 1, why does the for loop index need to be started at start, and why do we need pass a start parameter to helper method?

1
By the way, permute(n) = combine(n, n), so there's no need for two separate implementations - Niklas B.
Nope, they are different. Combine(3,3) will give he result of (1,2,3) only .... - catlovespurple
@NiklasB. Yeah, not being an english speaker by birth or education, I had the same initial thought, so I looked it up and found this good explanation of Combination vs. Permutation - Andreas
@catlovespurple, what does tag dfs mean? - Anton Danilov
@AntonDanilov depth first search... - catlovespurple

1 Answers

0
votes

Don't be surprised being looking at the Prolog code. I decided this will be useful to look at the problem from different view points.

Combination is an arbitrary subset of the set containing given number of elements. The order of elements is irrelevant.

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).

Permutation of the list L is a list containing all elements of list L in some order.

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).

So my answer is:

We need the start index in combination case to specify subset size.