Combination and Permutation

Concept:

The fundamental difference is:

• Combination does not care ORDER
• Permutation cares ORDER

Combination:

1. Without duplicate numbers (Any Length)

*There are 2^n solutions.

  for (int i = 0; i < 2^n; i++) {

    find the solution for i.

  }

 2.  Without duplicate numbers (Only Length k)

        if (solution.size() == k) {

            rst.add(new ArrayList(solution));

            return;

        }        

        for (int i = start; i <= n; i++) {// <=n because we want 1 ~ n in this problem

            solution.add(i);

            helper(rst, solution, n, k, i + 1);

            solution.remove(solution.size() - 1); //Back-track

        }

3. With duplicate numbers (but not allowing replication [each number can be used at most 1 time])

1) Build A HashSet

2) Sort the numbers

    Then, the idea is to avoid the same number in the same level.

    int prev = -1;//Repeat detection

        for (int i = start; i < num.length; i++) {

            if (prev != -1 && prev == num[i]) {

                continue;

            }

            list.add(num[i]);

            sum += num[i];

            helper(rst, list, num, target, sum, i + 1);

            //Back track:

            sum -= num[i];

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

            //Repeat Detection

            prev = num[i];

        }

4. With duplicate numbers (allowing replication)

1) Build A HashSet

2) Sort the numbers

    Then, the idea is to avoid the same number in the same level.

    int prev = -1;//Repeat detection

        for (int i = start; i < num.length; i++) {

            if (prev != -1 && prev == num[i]) {

                continue;

            }

            list.add(num[i]);

            sum += num[i];

            helper(rst, list, num, target, sum, i);   //allow replication

            //Back track:

            sum -= num[i];

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

            //Repeat Detection

            prev = num[i];

        }

Permutation:

1. Basic Version (No duplication)

for (int i = 0; i < nums.size(); i++) {

            if (accessed[i] == true) {

                continue;

            }

            

            accessed[i] = true;

            list.add(nums.get(i));

            permuteRecursively(results, list, accessed, nums);

            accessed[i] = false;

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

        }

2. Basic Version (No duplication) But No recursion

Queue<ArrayList<Integer>> queue = new LinkedList<ArrayList<Integer>>();

        ArrayList<Integer> list;

        for (int num : nums) {

            list = new ArrayList<Integer>();

            list.add(num);

            queue.offer(new ArrayList<Integer>(list));

        }

        while (!queue.isEmpty()) {

            list = queue.poll();

            if (list.size() == nums.size()) {

                rst.add(new ArrayList<Integer>(list));

                continue;

            }

            for (int i = 0; i < nums.size(); i++) {

                if (!list.contains(nums.get(i))) {

                    list.add(nums.get(i));

                    queue.offer(new ArrayList<Integer>(list));

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

                }

            }

        }

3. (With duplication)

    Sort nums 

    It is the magic part:

if (list.size() == nums.size()) {

            rst.add(new ArrayList<Integer>(list));

            return;

        }

        for (int i = 0; i < nums.size(); i++) {

            if (mark[i] || (i != 0 && mark[i - 1] && nums.get(i) == nums.get(i - 1))) {

                continue;

            }           

            list.add(nums.get(i));

            mark[i] = true;

            dfs(nums, list, rst, mark);

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

            mark[i] = false;

        }