# C# - recursive backtracking with Trie cache

• 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])
{
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;
}
}
``````

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