Subsets

Questions which are related with permutation or combination, think about the DFS.

• backtrace: add a new state and then remove the state after the DFS operation
• de-depulicate：use the fixed order
• Think by level(BFS, recursion tree), implement the code by DFS
• Be careful about the corner cases, check the parameters
• Use helper function (modulize)

Recursion three keys:

• Add all of the subsets which meet the requirements to the result
• Change the question to smaller questions
  • add: subset.add(nums[i]);
  • recursion: index＝i＋1
  • backtrace：subset.remove(nums[i]);
• exit when meet the condition

subsets template (permutation and combination template)

private void subset(List<List<Integer>> result, List<Integer> list, int[] nums, int pos) {

  // output
  result.add(new ArrayList<Integer>(list));

  // loop
  for (int i = pos; i < nums.length; ++i) {

    // special conditions
    if (i != pos && nums[i] == nums[i-1]) {
      continue;
    }

    // add new item
    list.add(nums[i]);

    // next level (DFS)
    subset(result, list, nums, i+1);

    // back, remove the added item
    list.remove(list.size()-1);
  }
}

• Suitable for all kinds of searching questions
• Where to change
  • Output condition
  • special condition
  • backtrace

Permutation Use swap: swap(index, i) -> dfs(index+1) -> swap(index, i)