Permutation

Key: Key: Each position, we only select one candidate once.

Draw recursion tree:

                                1          2        3
                               /           |         \
                            1[23]        2[13]         3[12]
                            /   |         /    \     /      \
                         12[3]  13[2]   21[3] 23[1] 31[2] 32[1]
                         /       \        /     \    /      \
                        123     132     213   231   312     321

   public void dfs (int[] array, int k) {
    dfs(array,k);    
}
void dfs(int[] array, int start, int k) {
    if (k == 0){
        int[] res = new int[array.length];
        res = System.arrayCopy(array,0,array.length,res,0);
        return;
    }
    Set<Integer> hs = new HashSet<>();
    for(int i = start; i < array.length; i++) {
        if (hs.add(array[i]) {
            swap(array,i,start);
            dfs(array,start + 1, k - 1);
            swap(array,i,start);
        }
    }
}

what if with dup ? like [1,1,2,3] permutation

                1[123]  1[123] 2[113] 3[112]
                         dup

Combination

Subset II

{
                1         ""
              /    \     /     \
             2    ""     2      ""
            /\     /\    / \    /\
           3  ""   3 "" 3   "" 3 ""
}

public void dfs(List<List<Integer>> res, List<Integer> resCell, int[] array, int i, int k) {
    if (resCell.size() == k || i >= array.length)  {
        res.add(new ArrayList<Integer>(resCell));
        return;
    }
    resCell.add(array[i]);
    dfs(res,resCell,array,i + 1);
    resCell.remove(resCell.size() - 1);
    dfs(res,resCell,array,i + 1);
}

Solution II: depend on set

Key : look for valid candidate set

                1         2            3
              1[23]      2[13]          3[12]
            /   \         / \         /     \
          12[3] 13[2]   21[3] 23[1]  31[2] 32[1]
           /     \       /       \    /      \
         123     132    213    231   312     321

1) sort, only add candidate larger than itself.

2) record last element position, we only add all candidates after that position.

Dedup Version

                       1[23]    2[3]    3[""]
                      /  \        \         \
                   12[3] 13[""]  23[""]      3
                    /
                123
{base case " size = 2 , start <= array.length" recursion tree.
                             1[23]       2[3]    3 (start = 2)
                          /       \       |      |
                       12[3]     13[]   23       "" array.length >= 3
}

public void dfs (int[] array, int start) {
    if (start == array.length) {
        return;
    }
    for(int i = start; i < array.length; i++) {
        res.add(array[i]);
        //add to final result container
        dfs(array,start + 1);
        res.remove(res.size() - 1);
    }
}

K size

what does base case mean ?

still that recursion tree.

With dup elements or not ?

1 1 2 3

k size.

Add or not add recursion tree with dup

         1                  ""
     /      \             /   \
    1        ""          1     ""
   /  \     /  \       / \      /  \
 2    ""    2   ""     2   ""   2 ""
/ \    /\   /\   /\    /\   /\  /\
3 ""  3 ""  3 '' 3 ''  3 '' 3 ''

}

public void dfs (int[] array, int start) {
    if (start == array.length) {
        return;
    }
    res.add(array[start]);
    dfs(array,start + 1);
    res.remove(res.size() - 1);
    while(start < array.length && array[start + 1] == array[start]) {
        start++;
    }
    dfs(array, start + 1);
}

Size recursion tree without dup

eg. 1 2 2 3

{
       1[223]  2[23]         2[3]  3[]
       /    \    /  \          /      \
   12[23]   13[3] 22[3] 23[]   23       3
   / \        /\    \    \
122[3] 123[] 133    223   23

}

public void dfs (List<List<Integer>> res, List<Integer> resCell, int[] nums, int start, int k) {
    if (resCell.size() == k) {
        res.add(new ArrayList<Integer>(resCell));
        return;
    }
    int i = start;
    while(i < nums.length) {
        resCell.add(nums[i]);
        dfs(res,resCell,nums, i + 1, k);
        resCell.remove(resCell.size() - 1);
        while(i < nums.length && nums[i + 1] == nums[i]) {
            i++:
        }
        i++;
    }
}