#78. Subsets

題目描述

給你一個陣列元素值不重複的整數陣列nums，回傳所有可能的子集合(冪集)。

回傳的結果不能包含重複的子集合，但可以以任意順序排列。

限制條件

1 <= nums.length <= 10
-10 <= nums[i] <= 10
所有的整數不會重複。

解題思路

這一題是排列組合題，所以我們只要找到排列組合的規律，就可以解決問題。

舉例來說： nums = [1,2,3], ans = [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]。

我們可以在答案中找到以下的規律：

不選擇任何數字的[]。
選擇1個數字的[1]、[2]、[3]。
選擇2個數字的[1,2]、[1,3]、[2,3]。
選擇3個數字的[1,2,3]。

所以我們可以看出排列組合可以先從所有數字中選出一個數字作為基礎組合，接著以這個基礎組合加上挑選剩餘的其他數字，就可以完成新的組合，接著再以新的元素作為新的基礎組合，重複直到完成所有組合。

比較需要注意的是剩餘的數字不能包含當前所選取數字之前的數字，舉例來說當我們挑選數字[1]的時候，剩下的數字為[2,3]，所以我們在下一輪可以配對出[1,2]、[1,3]兩種類別。
但是如果我們在挑選數字[2]的時候，剩下的數字為[1,3]，下一輪會產生的結果就會是[2,1]、[2,3]。[2,3]是我們想要的結果，但[2,1]和[1,2]是重複的，這樣就沒有達到題目要求。
因此我們挑選了數字[2]之後，留下的數字就應該使會剩下[3]而已，也就是說當我們挑了當下的數字之後，當下數字位置之後的數字才是下一輪的配對元素，位置之前的都要捨棄掉避免出現重複的答案。

public class Solution {    
    public IList<IList<int>> Subsets(int[] nums) {
        var ans = new List<IList<int>>();
        Helper(nums,new List<int>(),ans);
        return ans;
    }
    public void Helper(int[] nums, List<int> tempSet, List<IList<int>> ans){        
        ans.Add(tempSet);
        if(nums.Length == 0) return;        
        for(int i=0;i<nums.Length;i++){
            var newTempSet = new List<int>(tempSet);
            newTempSet.Add(nums[i]);            
            Helper(nums.Skip(i+1).ToArray(),newTempSet,ans);
        }
    }
}

複雜度分析：

時間複雜度：當陣列為[1]時，可以知道有[],[1]2種組合，陣列為[1,2]時為4種，陣列為[1,2,3]時為8種，陣列為[1,2,3,4]時為16種，因此時間複雜度為O(2^n)。
空間複雜度：空間複雜度為O(2^n)。

學習重點

Array