A Standard 12-Line DFS+Backtracking Solution


  • 0
    L
    public IList<IList<int>> CombinationSum2(int[] candidates, int target){
        Array.Sort(candidates);
        List<IList<int>> allList = new List<IList<int>>();
        List<int> list = new List<int>();
        dfsBacktrack(allList, list, 0, candidates, target);
        return allList;
    }
    
    private void dfsBacktrack(IList<IList<int>> allList, List<int> curList, int beginIndex, int[] candidates, int newTarget){
        if (newTarget == 0) allList.Add(new List<int>(curList));
        for (int i = beginIndex; i < candidates.Length && newTarget >= candidates[i]; i++){
            if (i > beginIndex && candidates[i] == candidates[i - 1]) continue;
            curList.Add(candidates[i]);
            dfsBacktrack(allList, curList, i + 1, candidates, newTarget - candidates[i]); //DFS
            curList.RemoveAt(curList.Count - 1); //Backtrack
        }
    }

Log in to reply
 

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