C# DFS solution


  • 0
    Y
    // consider as find a solution in n*n array, since every num can only be selected once, we will need to use index=1 in next search, and need to remove duplicated after the first added to list.
    
    public class Solution {
        public IList<IList<int>> CombinationSum2(int[] candidates, int target) {
            
            Array.Sort(candidates);
            
            var result=new List<IList<int>>();
            
            DFS(-1,0,candidates,target,result,new List<int>());
            
            return result;
        }
        
        
        public void DFS(int index,int depth, int[] candidates,int target, IList<IList<int>> result, IList<int> curr)
        {
            if(target==0)
            {
                result.Add(curr);
                return;
            }
            
            for(int i = index + 1; i < candidates.Length && candidates[i] <= target; i++)
            {
                var newList=new List<int>();
                
                foreach(var item in curr)
                {
                    newList.Add(item);
                }
                
                newList.Add(candidates[i]);
                
                DFS(i, depth + 1, candidates, target - candidates[i], result, newList);
                
                //colone
                while(i < candidates.Length - 1 && candidates[i] == candidates[i+1])
                {
                    i += 1;
                }
                
            }
               
        }
        
      }

Log in to reply
 

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