Backtracking can also help us to get all subsets of a given slice. If Combination and Partitioning problems can be converted to get root-to-leaf paths during a tree DFS traversal, Subsets can be treated as getting all root-to-node paths during a tree DFS traversal.

78. Subsets

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func subsets(nums []int) [][]int {
    result := [][]int{[]int{}}
    path := []int{}
    length := len(nums)
    var backtracking func(int)
    backtracking = func(index int) {
        if index == length {
            return
        }
        for i := 0; i < length; i++ {
            path = append(path, nums[i])
            temp := make([]int, len(path))
            copy(temp, path)
            result = append(result, temp)
            backtracking(i + 1)
            path = path[:len(path) - 1]
        } 
    }
    backtracking(0)
    return result
}

90. Subsets II

It’s similar to #78, the only difference is we can’t have duplicated subsets, which means we can’t pick the same value at the same tree level during traversal.

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
import "sort"
func subsetsWithDup(nums []int) [][]int {
    sort.Ints(nums)
    result := [][]int{[]int{}}
    path := []int{}
    length := len(nums)
    var backtracking func(int)
    backtracking = func(index int) {
        if index == length {
            return
        }
        for i := index; i < length; i++ {
            if i > index && nums[i] == nums[i - 1] {
                continue
            }
            path := append(path, nums[i])
            temp := make([]int, len(path))
            copy(temp, path)
            result = append(result, temp)
            backtracking(i + 1)
            path = path[:len(path) - 1]
        }
    }
    backtracking(0)
    return result
}

491. Increasing Subsequences

Since we can’t sort the given slice, so we have to use a hashmap / array to save the used nodes in the same layer.

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
27
28
func findSubsequences(nums []int) [][]int {
    result := [][]int{}
    path := []int{}
    length := len(nums)
    var backtracking func(int)
    backtracking = func(index int) {
        if len(apth) == length {
            return
        }
        used := make(map[int]bool)
        for i := index; i < length; i++ {
            if (len(path) > 0 && path[len(path) - 1] > nums[i]) || used[nums[i]] {
                continue
            }
            used[nums[i]] = true
            path = append(path, nums[i])
            if len(path) >= 2 {
                temp := make([]int, len(path))
                copy(temp, path)
                result = append(result, temp)
            }
            backtracking(i + 1)
            path = path[:len(path) - 1]
         }
    }
    backtracking(0)
    return result
}