C# - recursive backtracking with Trie cache


  • 0

    I think the part about finding the sets is pretty similar to other problems and is solved with backtracking solution. Notice that even though I check for uniqueness before adding to my results collection I still may as well apply the "skip ahead while finding repeats" portion of your loop to cut out as much low hanging fruit as possible.

    To avoid duplicates I use a custom Trie node "NumNode" to keep track of lists already used. Notice I can do the check for existence and the insert in the same call. This should result is better performance than stringifying your array as key.

    public class Solution 
    {
        NumNode cache = new NumNode();
        
        public IList<IList<int>> FindSubsequences(int[] nums) 
        {
            IList<IList<int>> lists = new List<IList<int>>();
            Find(nums, 0, lists, new List<int>());
            return lists;
        }
        
        public void Find(int[] nums, int index, IList<IList<int>> lists, IList<int> curr)
        {
            if (curr.Count >= 2 && cache.Insert(curr)) lists.Add(new List<int>(curr));
            
            for (int i = index; i < nums.Length; i++)
            {
                if (curr.Count == 0 || nums[i] >= curr[curr.Count - 1])
                {
                    curr.Add(nums[i]);
                    Find(nums, i + 1, lists, curr);
                    curr.RemoveAt(curr.Count - 1);
                    
                    while (i < nums.Length - 1 && nums[i] == nums[i+1]) i++;
                }
            }
        }
    }
    
    public class NumNode
    {
        public bool IsEnd = false;
        public Dictionary<int, NumNode> nodes = new Dictionary<int, NumNode>();
        
        // return true if inserted, false if already exists
        public bool Insert(IList<int> list)
        {
            NumNode n = this;
            foreach (int x in list)
            {
                if (!n.nodes.ContainsKey(x)) n.nodes[x] = new NumNode();
                n = n.nodes[x]; 
            }
            
            if (n.IsEnd) return false;
            
            n.IsEnd = true;
            return true;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.