关于go:求集合的固定长度的子集

32次阅读

共计 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
}

正文完
 0