回溯算法：leetcode 78 数组子集

Jan 13, 2020 · 1 min read · Golang 回溯算法数组 ·

本文讲解了用最简单的递归方法来寻找一个整数数组的子集以及背后的回溯算法思想。

给你一个整数数组 nums，数组中的元素互不相同。返回该数组所有可能的子集。解集不能包含重复的子集。你可以按任意顺序返回解集。

示例1：

1输入：nums = [1,2,3]
2输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例2：

1输入：nums = [0]
2输出：[[],[0]]

提示：

1 \(\leq\) nums.length \(\leq\) 10
-10 \(\leq\) nums[i] \(\leq\) 10
nums 中的所有元素互不相同

思路：运用回溯模板

 1func backtracking(参数){
 2  if 终止条件 {
 3    存放结果; 
 4    return;
 5  }
 6  for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
 7    处理节点; 
 8    backtracking(路径,选择参数)
 9    回溯,撤销处理结果;
10  }
11}

解法：

 1package main 
 2
 3import (
 4  "fmt"
 5)
 6
 7var result [][]int
 8var path []int
 9func backtracking(arr []int, startIndex int){
10  if startIndex >= len(path){
11    result = append(result, path)
12    return
13  }
14  for (i := startIndex; i < len(arr); i++){
15    append(path, arr[i])
16    backtrackiing(arr, startIndex + 1)
17    path = path[:len(path)-1]
18  }
19}
20
21func subset(arr []int)[][]int{
22  backtracking(arr,0)
23  return result
24}
25
26func main(){
27  fmt.Println([]int{1,2,3}) 
28}

翻译:

"English" |