0

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);
        }
    }
}
kofi boateng
  • 95
  • 3
  • 9
  • [Related explanation](https://stackoverflow.com/a/70173332/6243352). I don't think you need as many copies as you're making here and I don't think it's language-specific. The main reason to copy is because when you find a result and don't copy, you'll alias the "working copy" array multiple times in the result list, leaving you with a bunch of empty arrays when the backtracking pops all of the elements off on the way back up the call stack. Making the copy when you find a result ensures it's a snapshot of exactly the result and won't be mutated further. – ggorlen Jul 27 '22 at 00:59
  • @ggorlen Your explanation makes sense! Thank you for the link as well. It lead to some more reading material after that. – kofi boateng Jul 28 '22 at 13:19

0 Answers0