共计 1192 个字符,预计需要花费 3 分钟才能阅读完成。
目标
把握求一个汇合所有指定长度子集的思路
引子
给你一个整数数组 nums
,数组中的元素 互不雷同 。返回该数组所有可能的子集(幂集)。
解集 不能 蕴含反复的子集。你能够按 任意程序 返回解集。
示例 1:
输出:nums = [1,2,3]
输入:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2:
输出:nums = [0]
输入:[[],[0]]
提醒:
- 1 <= nums.length <= 10
- -10 <= nums[i] <= 10
- nums 中的所有元素 互不雷同
子集的遍历 – 找法则
遍历长度为 m 的汇合 \(C_m^n \)的所有长度为 n 的子集,有法则嘛?
子集的遍历 – 列通项公式 1
当指针索引列表的最初一位的索引值 indexes[n-1]小于 m 时,下一帧的法则:
indexes[i] += 1
子集的遍历 – 列通项公式 2
当指针索引列表的最初一位的索引值 indexes[n-1]等于 m 时,下一帧的法则:
批改指针索引列表以后的指针,让指针索引列表的以后指针指向 i 的后面一位并赋值给 i, 在实现列表中 i 后每一个成员的值为前一个成员的值加 1
i=n-1
for ;i>0&&i<m-1;i--{}
index[i]+=1
for j:=i+1;j<n-1;j++{index[j]=index[j-1]+1
}
子集的遍历 – 实现本人固定为 n 的所有子集代码
func getSubSets(nums []int, subSetLength int) [][]int {var result [][]int
var subSet = make([]int, subSetLength)
var n = len(nums)
for i := 0; i < subSetLength; i++ {subSet[i] = nums[i]
}
var initSubSet = make([]int, subSetLength)
copy(initSubSet, subSet)
result = append(result, initSubSet)
var indexes = make([]int, subSetLength)
for i := 0; i < subSetLength; i++ {indexes[i] = i
}
for {
i := subSetLength - 1
for ; i >= 0 && indexes[i] == n+i-subSetLength; i-- { }
if i < 0 {return result}
indexes[i] += 1
for j := i + 1; j < subSetLength; j++ {indexes[j] = indexes[j-1] + 1
}
for ; i < subSetLength; i++ {subSet[i] = nums[indexes[i]]
}
var tempSubSet = make([]int, subSetLength)
copy(tempSubSet, subSet)
result = append(result, tempSubSet)
}
return result
}
正文完