leetcode90. Subsets II

PascalXie 發(fā)布于2019-08-15 10:48 / 1428人閱讀

摘要：題目要求可以先參考關(guān)于的這篇博客再看接下來的內(nèi)容。思路一鏈表的形式我們可以通過例子，，，來說明。在遞歸中我們會將起始下標(biāo)后的值依次加入當(dāng)前結(jié)果集，并將結(jié)果集加入結(jié)果集數(shù)組中。如果遇到重復(fù)的數(shù)字，則繼續(xù)遍歷下一個(gè)數(shù)字，直至遍歷結(jié)束。

題目要求

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

可以先參考關(guān)于SubsetI的這篇博客再看接下來的內(nèi)容。
這里的區(qū)別在于假設(shè)輸入的數(shù)組存在重復(fù)值，則找到所有不重復(fù)的子集。

思路一：鏈表的形式

我們可以通過例子[1，2，2，3]來說明。當(dāng)我們遇到重復(fù)值時(shí)，我們可以使用一個(gè)臨時(shí)數(shù)組將所有重復(fù)值的結(jié)果臨時(shí)保存起來，在這道題目中就是[[2],[2,2]]，然后再將當(dāng)前res中的結(jié)果和它一一組合成新的結(jié)果值，本例子中的當(dāng)前res為[[ ],[1]]，這樣合成之后就是[[],[2],[2,2],[1,2],[1,2,2]]，從而避免產(chǎn)生重復(fù)的結(jié)果。
代碼如下：

    public List> subsetsWithDup(int[] nums) {
        List> result = new LinkedList>();
        result.add(new ArrayList());
        int length = nums.length;
        Arrays.sort(nums);
        for(int i = 0 ; i> temp = new LinkedList>();
            for(List tempResult : result){
                List copyTemp = new ArrayList(tempResult);
                copyTemp.add(nums[i]);
                temp.add(copyTemp);
            }
            i++;
            while(i0){
                    List currentTemp = temp.removeFirst();
                    result.add(currentTemp);
                    List moreCurrentTemp = new ArrayList(currentTemp);
                    moreCurrentTemp.add(nums[i]);
                    temp.add(moreCurrentTemp);
                }
            }
            result.addAll(temp);
        }
        return result;
    }

思路二：遞歸

其實(shí)對于遞歸，應(yīng)當(dāng)考慮從遞歸的輸入和輸出考慮。在這里我們將遞歸的輸入為當(dāng)前的結(jié)果集，當(dāng)前的數(shù)組，和遍歷的起始下標(biāo)。在遞歸中我們會將起始下標(biāo)后的值依次加入當(dāng)前結(jié)果集，并將結(jié)果集加入結(jié)果集數(shù)組中。如果遇到重復(fù)的數(shù)字，則繼續(xù)遍歷下一個(gè)數(shù)字，直至遍歷結(jié)束。思路簡單清晰，效率也很高。

    public List>  subsetsWithDup2(int[] nums) {
        List> fnl = new ArrayList>();
        Arrays.sort(nums);
        helper(fnl, new ArrayList(), nums, 0);
        return fnl;
    }
    
    public void helper(List> fnl, List temp, int[] nums, int start){
        fnl.add(new ArrayList(temp));
        for(int i =start; istart && nums[i]==nums[i-1]) continue;
            temp.add(nums[i]);
            helper(fnl, temp, nums, i+1 );
            temp.remove(temp.size()-1);
        }
        
    }

想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會不定期的發(fā)放福利哦~