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:
[
[3],
[1],
[2],
[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
){
list.add(new ArrayList<>(tempList));
for(int i = startIndex; i < nums.length; i++){
tempList.add(nums[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
tempList.add(nums[i]);
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){
list.add(new ArrayList<>(tempList));
return;
}
for(int i = 0; i < nums.length; i++){
if(tempList.contains(nums[i])){
continue; // element already exists, skip
}
tempList.add(nums[i]);
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){
list.add(new ArrayList<>(tempList));
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;
tempList.add(nums[i]);
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:
- Same repeated number may be chosen from
candidatesrepeatedly. - All numbers are positive integers, including target number.
- The solution set cannot contain duplicate combinations.
Example 1:
==========
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[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){
list.add(new ArrayList<>(tempList));
return;
}
for(int i = startIndex; i < nums.length; i++){
if(nums[i] > targetRemaining){
break; // no need to go further
}
tempList.add(nums[i]);
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
}
tempList.add(nums[i]);
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){
list.add(new ArrayList<>(tempList));
return;
}
for(int i = startIndex; i < 10; i++){
if(i > targetRemaining){
break; // no need to go further
}
tempList.add(i);
helper(list, tempList, k, targetRemaining - i, i + 1);
tempList.remove(tempList.size() - 1);
}
}
Well, that's all for now. I hope these exercises will help you with these questions. See ya!
Post was published on , last updated on .
Like the content? Support the author by paypal.me!
