C# Clean solution


  • 0
    J

    Backtrack
    Time Complexity: O(N!)
    Space: O(N)?

        public IList<IList<int>> CombinationSum2(int[] c, int t)
        {
            Array.Sort(c);
            var r = new List<IList<int>>();
            H(r, c.ToList(), t, new List<int>(), 0);
            return r;
        }
    
        public void H(IList<IList<int>> r, List<int> c, int t, List<int> l, int st)
        {
            if (t == 0)
            {
                r.Add(new List<int>(l));
            }
    
            for (int i = st; i < c.Count; i++)
            {
                if ((i > 0 && c[i] == c[i - 1]))
                {
                    st++;
                }
                else if (c[i] <= t)
                {
                    var a = c[i];
                    l.Add(a);
                    c.RemoveAt(i);
                    H(r, c, t - a, l, st++);
                    l.RemoveAt(l.Count - 1);
                    c.Insert(i, a);
                }
            }
        }

Log in to reply
 

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