# 78-Subsets
###### tags: `Medium`

* Question:
https://leetcode.com/problems/subsets/

Key:
1.使用Backtracking / DFS / Recursive
2.bitwise operation

>reference :
1.
A.
https://medium.com/@ChYuan/leetcode-78-subsets-%E5%BF%83%E5%BE%97-medium-222577b31c81
B. https://leetcode.com/problems/subsets/discuss/458789/c%2B%2B-dfs
2. https://leetcode.com/problems/subsets/discuss/961493/C%2B%2B-Bitmask-Solution

Hint:
1. 這題的集合可能性可看作一種對高維度的窮舉，因此可以使用Backtracking處理
2. 每個位元都是選擇或不選擇兩種可能性，故有2^n次方種，另外也可以將選擇的數作為左子樹，不選的數作為右子數，因此也可以用DFS解，寫起來剛好跟Backtracking用於樹狀結構時相似
3. &1 == %2
4. >>1 == /2

* Backtracking跟DFS的相似與不同補充:
1. 很多人誤認 backtracking 就是圖論中的 DFS ，然而兩者沒有關係。兩者相似的地方是： backtracking 遇到不合理的解答會馬上回溯， DFS 遇到拜訪過的節點會馬上回溯。
2. https://stackoverflow.com/questions/1294720/whats-the-difference-between-backtracking-and-depth-first-search

>related problem :
## My Solution

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        res.add(new ArrayList<Integer>());
        for(int i = 0; i < nums.length; i++) {
            List<Integer> list = new ArrayList<Integer>();
            list.add(nums[i]);
            dfs(res, list, nums, i + 1);
        }
        return res;
    }
    
    private void dfs(List<List<Integer>>res, List<Integer> list, int[] nums, int start) {
        res.add(list);
        if(start >= nums.length) {     
            return;
        }
        for(int j = start; j < nums.length; j++) {
            List<Integer> copy = new ArrayList<Integer>(list);
            copy.add(nums[j]);
            dfs(res, copy, nums, j + 1);
        }
    }
}

## Backtracking Solution

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) 
    {
        vector<vector<int>> ans;
        vector<int> buf;
        for ( int i = 0; i <= nums.size(); i++ )
        {            
            FindSolutions( ans, nums, i, 0, buf );
        }
        
        return ans;
    }

    void FindSolutions( vector<vector<int>>& ans, const vector<int>& nums, 
                        const int& k, const int& t, vector<int> buf )
    {
        if ( 0 == k )
        {
            ans.push_back({});
            return;
        }
        
        if ( buf.size() == k )
        {
            ans.push_back(buf);
            return;
        }
        
        for ( int i = t; i < nums.size(); i++ )
        {
            //decision to choose the element into subset
            buf.push_back( nums[i] );
            FindSolutions( ans, nums, k, i+1, buf );
        //decision NOT to choose the element into subset
            buf.pop_back();
        }
    }
    
};

## DFS solution

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> result;
        dfs(result, 0, nums, {});
        return result;
    }
    void dfs(vector<vector<int>>& result, int index, vector<int>& nums, vector<int> current){
        result.push_back(current);
        for(int i=index;i<nums.size();i++){
            current.push_back(nums[i]);
            dfs(result, i+1, nums, current);
            current.pop_back();
        }
    }
};

## bit mask solution

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
		vector<vector<int>> ans;
		vector<int> a;

		int n = nums.size();
		for(int i=0; i < (1<<n); i++){
			a.clear();
			for(int j=0;j<n;j++){
				if(i & (1<<j)) a.push_back(nums[j]);
			}
			ans.push_back(a);

		}
		return ans;
    }
};