I am reviewing Leetcode problem #78 Subsets and am currently at the point where I have the general understanding backtracking problems. The issue I am having may seem to be language specific but I will explain the general idea. Here is the code first.
class Solution {
List<List<Integer>> list = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
dfs(new ArrayList<Integer>(), 0, nums);
return list;
}
private void dfs(List<Integer> perm, int choice, int[] choices){
if(choice >= choices.length){
list.add(new ArrayList<>(perm));
return;
}
List<Integer> temp = new ArrayList<>(perm);
temp.add(choices[choice]);
dfs(temp,choice+1,choices);
temp.remove(temp.size()-1);
dfs(temp,choice+1,choices);
}
}
In the base case, (choice >= choice.length), in order to get the correct answer I had to add a copy of a previous copy I already passed, however on other backtracking questions (See Permutations) I do not have to make a copy of a copy. I believe the reason could be disguised within the wording of the question, but if anyone knows why this is the case the help will be greatly appreciated. See below for Permutations
class Solution {
List<List<Integer>> list = new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
List<Integer> dt = new ArrayList<>();
for(int n:nums) dt.add(n);
dfs(new ArrayList<>(), dt);
return list;
}
private void dfs(List<Integer> perm, List<Integer> dt){
if(dt.size() == 0){
list.add(perm);
return;
}
for(Integer n:dt){
List<Integer> tempP = new ArrayList<>(perm);
List<Integer> tempD = new ArrayList<>(dt);
tempP.add(n);
tempD.remove(n);
dfs(tempP,tempD);
}
}
}