[LeetCode] 78. Subsets

轉自LeetCode

Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

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

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

<Solution>

這題和 Combinations 有點類似

但不一樣的地方是，這次沒有指定 subset 的長度，而是要把所有長度都找出來

一樣還是使用 DFS，但再多一層 for 迴圈來歷遍所有可能長度

code 如下
c++

	class Solution {
	private:
	vector<vector<int>> ans;
	vector<int> out;
	public:
	vector<vector<int>> subsets(vector<int>& nums) {
	ans.push_back(out);
	if(nums.empty()) {
	return ans;
	}
	else if(nums.size() == 1) {
	ans.push_back(nums);
	return ans;
	}
	//> search every possible length
	for(int k = 1; k <= nums.size(); k++) {
	out.resize(k);
	//> dfs
	dfs(0, 0, k, nums);
	}
	return ans;
	}
	void dfs(const int &start, const int &len, const int &targetLen, const vector<int>& nums) {
	if(len == targetLen) {
	ans.push_back(out);
	return;
	}
	for(int i = start; i < nums.size(); i++) {
	out[len] = nums[i];
	dfs(i+1, len+1, targetLen, nums);
	}
	}
	};

view raw findSubsets_1.cpp hosted with ❤ by GitHub

kotlin

	class Solution {
	val ans = mutableListOf<List<Int>>()
	fun subsets(nums: IntArray): List<List<Int>> {
	dfs(0, nums, emptyList())
	return ans
	}
	fun dfs(start: Int, nums: IntArray, cmb: List<Int>) {
	ans.add(cmb)
	for(i in start..nums.lastIndex) {
	dfs(i+1, nums, cmb+listOf(nums[i]))
	}
	}
	}

view raw Subsets.kt hosted with ❤ by GitHub

這邊還有一個另一種想法

有 n 個數字，那麼 subset 會有 2^n 個，因為每個數字可以要或不要

舉例 :

所以可以用 bit mask 的概念，來找出所有的 subsets

code 如下

	class Solution {
	public:
	vector<vector<int>> subsets(vector<int>& nums) {
	vector<vector<int>> ans;
	vector<int> out;
	int max = 1 << nums.size();
	int index, mask;
	//> every num has two states : yes or no
	//> so there are 2^n subsets fo n nums
	for(int i = 0; i < max; i++) {
	index = 0;
	mask = i;
	out.clear();
	while(mask > 0) {
	if((mask & 1) == 1) {
	out.push_back(nums[index]);
	}
	++index;
	mask >>= 1;
	}
	ans.push_back(out);
	}
	return ans;
	}
	};

view raw findSubsets_2.cpp hosted with ❤ by GitHub

還有一個想法，就是每次都把目前的數字，放到之前的 subsets，來形成新的 subsets

例如 nums = [1,2,3]，目前的 subsets 有 []、[1]、[2]、[1,2]，然後現在要處理 3

就是把 3 依序放入之前的 subsets : [3]、[1,3]、[2,3]、[1,2,3]

這樣全部的 subsets 就是 []、[1]、[2]、[1,2]、[3]、[1,3]、[2,3]、[1,2,3]

code 如下

C++

	class Solution {
	public:
	vector<vector<int>> subsets(vector<int>& nums) {
	vector<vector<int>> ans = {{}};
	for(int i = 0; i < nums.size(); i++) {
	int prvSize = ans.size();
	for(int j = 0; j < prvSize; j++) {
	vector<int> out = ans[j];
	out.push_back(nums[i]);
	ans.push_back(out);
	}
	}
	return ans;
	}
	};

view raw findSubsets_3.cpp hosted with ❤ by GitHub

Java

	class Solution {
	public List<List<Integer>> subsets(int[] nums) {
	List<List<Integer>> ans = new ArrayList<>();
	if(nums == null) {
	return ans;
	}
	ans.add(new ArrayList<>());
	int len;
	for(int i = 0; i < nums.length; i++) {
	len = ans.size();
	for(int j = 0; j < len; j++) {
	ArrayList<Integer> output = new ArrayList<>(ans.get(j));
	output.add(nums[i]);
	ans.add(output);
	}
	}
	return ans;
	}
	}

view raw subsets.java hosted with ❤ by GitHub