Leetcode discuss: 46. Permutations

Here is the post.

C# DFS algorithm with backtracking practice on June 2020

June 24, 2020

46. Permutations
    Problem statement
    Given a collection of distinct integers, return all possible permutations.

Introduction

It is my mock interview. I came out the depth first search algorithm and I wrote the solution in less than 20 minutes, but it took me over 20 minutes to fix the bug; I could not fix it and then I decided to try to use Visual studio debugger, the problem is that I mixed IList API Remove with RemoveAt, I should call RemoveAt with index position, instead of calling Remove.

Case study
[1, 2]
How to find all permutations?
The idea is to use HashSet to mark visited integer, since all integers are disctinct. Also it is important to learn optimal space O(N) using backtracking. One one permutation is complete, then the list should be copied to another new list. C# ToList() is good API to make a new copy.

DFS template
visit one more integer
add it to hashset

Run DFS

remove last integer - C# RemoveAt
remove the integer from hashSet.

Here are my highlights of practice:

1. It took me 10 to 20 minutes to write the code;
2. The bug is that [3, 3, 3] is one of result for test case [1, 2, 3];
3. I walked through white board testing witht test case with the array [1], and then test case 2: array [1, 2];
4. I played with List copy, and then question myself about DFS and backtracking;
5. The trouble shooting of API IList Remove -> RemoveAt took me almost 30 minutes;
6. The whole practice took me 60 minutes. I need to warm up troubleshooting skills.

C# practice
Here are highlights to improve my C# troubleshooting skills.

1. Read more about C# class List APIs, for example, IList ToList() API, Array.CopyTo, List.CopyTo;
2. Double check to make sure that backtracking in the algorithm needs a copy of list;
3. Backtracking - Stay simple
4. C# - IList Remove API vs RemoveAt API
5. It should take me 10 minutes to write bug-free code. I have to work hard on the goal.

public class Solution {
    public IList<IList<int>> Permute(int[] nums) {
        if(nums == null)
            return new List<IList<int>>(); 
        
        var permutations = new List<IList<int>>(); 
        var set = new HashSet<int>(); 
        var list = new List<int>();         
        
        runDFS(nums, set, list, permutations ); 
        
        return permutations; 
    }
    
    //[1]
    //[1, 2]
    //[1, 2, 3]
    private static void runDFS(int[] numbers, HashSet<int> found, IList<int> list, List<IList<int>> result)
    {
        if(numbers.Length == list.Count) // true
        {                        
            result.Add(list.ToList());// {1, 2}
            return;
        }        
        
        for(int i = 0; i < numbers.Length; i++) //i = 1
        {
            var current = numbers[i]; // 2
            if(found.Contains(current)) //false
            {
                continue; 
            }
            
            // DFS 
            list.Add(current);// [1,2
            found.Add(current); // {1,2}
            
            runDFS(numbers, found, list, result); // 
            
            list.RemoveAt(list.Count - 1); // remove 2 - RemoveAt, not Remove
            found.Remove(current); // remove 2           
        }              
    }
}