Back tracking is the common approach to solve problems about combinations, subsets, permutations or all possible solutions. When asked optimize result or max/min values, we should consider dynamic programming approach first as it usually has better time complexity. The time complexity of back tracking problem are various. For example, Hamiltonian cycle: O(N!), WordBreak: O(2^N) and NQueens: O(N!).
The following code calculate all subsets in a given array, which can be used as a template in many questions.
public static List<List<Integer>> allCombines(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
backtrack(result, new ArrayList<>(),nums, 0);
return result;
}
public static void backtrack(List<List<Integer>> result, List<Integer> tmpList, int[] nums, int index) {
result.add(new ArrayList<>(tmpList)); //add to result set, usually only when some conditions meet.
for (int i = index; i < nums.length; i++) { //loop all possible elements for next position.
tmpList.add(nums[i]); //add.
backtrack(result, tmpList, nums, i + 1); //back tracking and update parameter.
tmpList.remove(tmpList.size() - 1); //move back to previous position
}
}
Tip: If there are duplicate elements in the array and we want to remove duplicate subsets, need to sort the array first.
if(i > index && nums[i] == nums[i-1]) continue;
Leetcode 46. Permutations
Leetcode 47. Permutations II
Leetcode 78. Subsets
Leetcode 90. Subsets II
Leetcode 22. Generate Parentheses
Leetcode 301. Remove Invalid Parentheses