I am sure a lot of interviewees have done those questions before. Though there are also already many solutions out there, why am I still posting this in 2019? Well, personally I think it is still very important to know if you're familiar with backtracking and depth-first search. Before we dive into each question, let's try to understand what backtracking and depth first search (DFS) is and also the relationship between them.

Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution. [source: wikipedia]

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking. [source: wikipedia]

In short, Backtracking is a more general purpose algorithm and Depth-First search is a specific form of backtracking related to searching tree or graph data structures. Without further ado, let's get to the first question here: subset.

## Subsets

### Given a set of distinct integers, return all possible subsets.

``````Input: [1, 2, 3]
Output:
[
,
,
,
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
``````

NOTE: the solution set cannot contain duplicate subsets.

``````public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
helper(list, new ArrayList<>(), nums, 0);
return list;
}

private void helper(List<List<Integer>> list ,
List<Integer> tempList,
int [] nums,
int startIndex
){
for(int i = startIndex; i < nums.length; i++){
helper(list, tempList, nums, i + 1);
tempList.remove(tempList.size() - 1);
}
}
``````

This is a very typical `DFS` backtracking solution. The idea is to add the current temp list into the main list and keep backtracking.

#### Follow-up: what if the given set contains duplicates?

Well, we will just need to de-duplicate by making sure the current `i` is not the same as previous `i`:

``````    ...
for(int i = start; i < nums.length; i++){
if(i > start && nums[i] == nums[i-1]) continue; // skip duplicates
helper(list, tempList, nums, i + 1);
tempList.remove(tempList.size() - 1);
}
...
``````

## Permutations

### Given a collection of distinct integers, return all possible permutations.

``````Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
``````

In permutation, we need to make sure that the inner array size has the same size as the given array. Hence, we will only add the temp list to the main list when the temp list size equals to the given array size.

``````public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
// Arrays.sort(nums); // not necessary
helper(list, new ArrayList<>(), nums);
return list;
}

private void helper(List<List<Integer>> list,
List<Integer> tempList,
int [] nums
){
if(tempList.size() == nums.length){
return;
}

for(int i = 0; i < nums.length; i++){
if(tempList.contains(nums[i])){
continue; // element already exists, skip
}
helper(list, tempList, nums);
tempList.remove(tempList.size() - 1);
}

}
``````

If you think `contains()` method is taking too long, you can initiate a temp boolean array to keep track of the visit index. The follow up question below is using this method.

#### Follow-up: what if the given set contains duplicates?

``````Input: [1,1,2]
Output:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
``````

It is very similar to subsets with duplicates problem, except the order of the list is required. Here, we allocate a new boolean array to keep track of whether an element has been used in backtracking.

``````public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
helper(list, new ArrayList<>(), nums, new boolean[nums.length]);
return list;
}

private void helper(List<List<Integer>> list,
List<Integer> tempList,
int [] nums,
boolean [] used
){
if(tempList.size() == nums.length){
return;
}

for(int i = 0; i < nums.length; i++){
if(used[i] || i > 0 && !used[i - 1] && nums[i] == nums[i-1] ){
continue; // skip the used number and the same number
}
used[i] = true;
dfs(list, tempList, nums, used);
used[i] = false;
tempList.remove(tempList.size() - 1);
}

}
``````

## Combination Sums

### Given a collection of distinct integers `candidates` and a target number `target`, return all unique combinations in `candidates` where the candidate numbers sums to `target`.

NOTE:

1. Same repeated number may be chosen from `candidates` repeatedly.
2. All numbers are positive integers, including target number.
3. The solution set cannot contain duplicate combinations.
``````Example 1:
==========
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
,
[2,2,3]
]

Example 2:
==========
Input: candidates = [2,3,5], target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
``````

Again, this combination problem is very similar to the subsets and permutations. One thing that we might need to be aware of is that the same number can be used repeatedly, hence we don't need to increment the `startIndex` by 1 everytime we

``````public List<List<Integer>> combinationSum(int[] nums, int target) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
helper(list, new ArrayList<>(), nums, target, 0);
return list;
}

private void helper(List<List<Integer>> list,
List<Integer> tempList,
int [] nums,
int targetRemaining,
int startIndex
){

if(targetRemaining == 0){
return;
}

for(int i = startIndex; i < nums.length; i++){
if(nums[i] > targetRemaining){
break; // no need to go further
}

helper(list, tempList, nums, targetRemaining - nums[i], i); // not i + 1 because we can reuse same element
tempList.remove(tempList.size() - 1);
}

}
``````

#### Follow-up: what if the given set contains duplicates?

``````    ...
for(int i = startIndex; i < nums.length; i++){
if(i > startIndex && nums[i] == nums[i-1]) {
continue; // skip duplicates
}
helper(list, tempList, nums, targetRemaining - nums[i], i + 1);
tempList.remove(tempList.size() - 1);
}
...
``````

#### Follow-up: Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Same idea, same concept here.

``````public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> list = new ArrayList<>();
helper(list, new ArrayList<>(), k, n, 1);
return list;
}

private void helper(List<List<Integer>> list,
List<Integer> tempList,
int k,
int targetRemaining,
int startIndex
){

if(targetRemaining == 0 && tempList.size() == k){
return;
}

for(int i = startIndex; i < 10; i++){
if(i > targetRemaining){
break; // no need to go further
}