BFS Iterative Solution & DFS Solution


  • 0
    L

    Solution #1 BFS

    public IList<IList<int>> SubsetsWithDup(int[] nums) {
        List<IList<int>> result = new List<IList<int>>();
        result.Add(new List<int>());
        Array.Sort(nums);
        int len, lastLength = 0;
        for (int i = 0; i < nums.Length; i++){
            List<IList<int>> newResult = new List<IList<int>>();
            len = i > 0 && nums[i] == nums[i - 1] ? lastLength : 0;
            lastLength = result.Count;
            while(len < result.Count){
                List<int> nr = new List<int>(result[len++]);
                nr.Add(nums[i]);
                newResult.Add(nr);
            }
            result.AddRange(newResult);
        }
        return result;
    }
    

    Solution #2 DFS

    public IList<IList<int>> SubsetsWithDup(int[] nums) {
        Array.Sort(nums);
        IList<IList<int>> result = new List<IList<int>>();
        dfs(new List<int>(), nums, 0, result);
        return result;
    }
    
    private void dfs(IList<int> curList, int[] nums, int iCur, IList<IList<int>> result){
        if(iCur == nums.Length){
            result.Add(new List<int>(curList));
            return;
        }
        if(curList.Count == 0 || curList[curList.Count - 1] != nums[iCur])
            dfs(curList, nums, iCur + 1, result);
        curList.Add(nums[iCur]);
        dfs(curList, nums, iCur + 1, result);
        curList.RemoveAt(curList.Count - 1);
    }

Log in to reply
 

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