A huge number of coding interview problems involve dealing with Permutations and Combinations of a given set of elements. This pattern describes an efficient Breadth First Search (BFS) approach to handle all these problems.

Approaches to Backtracking Questions

Subsets

https://leetcode.com/problems/subsets/

Subsets

DFS backtracking approach:

1. Add value to temp list.
2. Go recursively.
3. Remove value from temp list.

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    backtrack(list, new ArrayList<>(), nums, 0);
    return list;
}

private void backtrack(List<List<Integer>> list , List<Integer> tempList, int [] nums, int start){
    list.add(new ArrayList<>(tempList));
    for(int i = start; i < nums.length; i++){
        tempList.add(nums[i]);
		    **// increment here coz we don't want same number twice**
        backtrack(list, tempList, nums, i + 1);
        tempList.remove(tempList.size() - 1);
    }
}

BFS approach:

1. Add empty list to result.
2. While traversing numbers, get result size.
3. And for set in subsets add value.

public static List<List<Integer>> findSubsets(int[] nums) {
  List<List<Integer>> subsets = new ArrayList<>();
  **// start by adding the empty subset**
  subsets.add(new ArrayList<>());
  for (int currentNumber : nums) {
    **// we will take all existing subsets and insert the current number in them 
		// to create new subsets**
    int n = subsets.size();
    for (int i = 0; i < n; i++) {
      **// create a new subset from the existing subset and insert the current element to it**
      List<Integer> set = new ArrayList<>(subsets.get(i));
      set.add(currentNumber);
      subsets.add(set);
    }
  }
  return subsets;
}

Subsets II (contains duplicates)

https://leetcode.com/problems/subsets-ii/

Subsets With Duplicates

Same things, but sort array first and and skip duplicates condition: