28-line Short C# Accepted Recursive Solution - O(n^2)


  • 0
    L
    public class Solution {
        public IList<IList<int>> CombinationSum(int[] candidates, int target) {
            List<int> history = new List<int>();
            Array.Sort(candidates);
            return RecursiveSum(candidates, history, target);
        }
    
        public List<IList<int>> RecursiveSum(int[] candidates, List<int> history, int target)
        {
            List<IList<int>> result = new List<IList<int>>();
            int i = 0;
            while (i < candidates.Length && candidates[i] <= target)
            {
                List<int> curHistory = new List<int>();
                foreach (int h in history)
                    curHistory.Add(h);
                if (curHistory.Count != 0 && candidates[i] < curHistory[curHistory.Count - 1])
                {
                    i++;
                    continue;
                }                
                curHistory.Add(candidates[i]);
                if (candidates[i] == target)
                    result.Add(curHistory);
                else
                    result.AddRange(RecursiveSum(candidates, curHistory, target - candidates[i]));
    
                i++;
            }
            return result;
        }
    }

  • 0
    C

    I thought this was an NP-complete problem, with no known polynomial time solution?

    Why do you say this is O(n^2)?


Log in to reply
 

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