未分類

Subsets

Array, Backtracking, BitManipulation, Go, LeetCode

Subsets

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:

1
2
3
4
5
6
7
8
9
10
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]
提示 解題應用
Array Array/Slice
Backtracking Recursive

Default:

1
2
3
func subsets(nums []int) [][]int {
}

解答思路:

建議可以先參考先前Combinations的解法，解說較為詳細，基本上概念完全一樣，只是將先前題的程式碼重覆利用而已，如果之前要找陣列中長度為k的所有組合，那麼現在要找陣列中長度為0~n的所有組合當然就只需要重覆呼叫之前的程式碼以此得到所有長度的所有組合。

程式碼解說:

這邊只解說與先前題目程式碼的相異之處，其實就只是將先前題的程式碼重覆利用而已，因為要列出所有長度的所有組合，所以就用迴圈從0到n開始將長度帶入先前程式碼的function之中，這邊要注意的是先前combine的function第一個參數是n，進而初始化一個包含1~n的陣列，這次就直接帶入原本題目給的陣列即可，最後將每次得到的回傳放入結果之中，待找出所有長度的所有組合就是我們要的結果

1
2
3
4
5
6
7
8
9
func subsets(nums []int) [][]int {
	var tmp [][]int
	var result [][]int
	for i := 0; i <= len(nums); i++ {
		tmp = combine(nums, i)
		result = append(result, tmp...)
	}
	return result
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func subsets(nums []int) [][]int {
	var tmp [][]int
	var result [][]int
	for i := 0; i <= len(nums); i++ {
		tmp = combine(nums, i)
		result = append(result, tmp...)
	}
	return result
}
func combine(nums []int, k int) [][]int {
	return recursive([]int{}, k, nums)
}
func recursive(curComb []int, k int, candidates []int) [][]int {
	var tmp [][]int
	var result [][]int
	if len(curComb) == k {
		tmpCurComb := make([]int, len(curComb))
		copy(tmpCurComb, curComb)
		return [][]int{tmpCurComb}
	}
	for i, v := range candidates {
		tmp = recursive(append(curComb, v), k, candidates[i+1:])
		result = append(result, tmp...)
	}
	return result
}

總結:

建議可以先參考先前Unique Paths的解法，解說較為詳細，基本上概念完全一樣，只是將先前題的程式碼重覆利用而已，如果之前要找陣列中長度為k的所有組合，那麼現在要找陣列中長度為0~n的所有組合當然就只需要重覆呼叫之前的程式碼以此得到所有長度的所有組合。

分享到