Intuition#

核心思路：排序後用 Two Pointers，對每個左端點（最小值），找到最遠的右端點使得 nums[left] + nums[right] <= target，中間的元素可選可不選，貢獻 2^(right-left) 個子序列。

• 子序列的最小值和最大值決定了合法性，中間元素隨便選
• 排序不影響子序列的 min/max 判斷（只是重新排列）
• 固定 left 後，right 越大代表可選範圍越廣，每個中間元素有「選/不選」兩種狀態

Approaches#

1: Brute Force（列舉所有子序列）#

• 概念: 用回溯列舉所有 2^n 個子序列，檢查 min + max <= target
• 時間複雜度: O(2^n) - 指數級，不可行
• 空間複雜度: O(n) - 遞迴深度

class Solution {
    fun numSubseq(nums: IntArray, target: Int): Int {
        val MOD = 1_000_000_007
        var count = 0
        fun backtrack(idx: Int, chosen: MutableList<Int>) {
            if (chosen.isNotEmpty()) {
                if (chosen.min() + chosen.max() <= target) {
                    count = (count + 1) % MOD
                }
            }
            for (i in idx until nums.size) {
                chosen.add(nums[i])
                backtrack(i + 1, chosen)
                chosen.removeAt(chosen.size - 1)
            }
        }
        backtrack(0, mutableListOf())
        return count
    }
}

⭐2: 排序 + Two Pointers + 預計算 2 的冪#

• 概念: 排序後，left 從頭、right 從尾；若 nums[left] + nums[right] <= target，以 left 為最小值的合法子序列有 2^(right-left) 個，然後 left++；否則 right–
• 時間複雜度: O(n log n) - 排序主導
• 空間複雜度: O(n) - 預計算 2 的冪陣列

class Solution {
    fun numSubseq(nums: IntArray, target: Int): Int {
        val MOD = 1_000_000_007
        nums.sort()
        val n = nums.size

        // 預計算 2 的冪 mod MOD
        val pow2 = IntArray(n)
        pow2[0] = 1
        for (i in 1 until n) {
            pow2[i] = (pow2[i - 1] * 2L % MOD).toInt()
        }

        var result = 0
        var left = 0
        var right = n - 1

        while (left <= right) {
            if (nums[left] + nums[right] <= target) {
                result = ((result.toLong() + pow2[right - left]) % MOD).toInt()
                left++
            } else {
                right--
            }
        }
        return result
    }
}

不能用 Math.pow(2, n) 直接算冪次，會溢位且精度不夠。必須預計算取模後的 2 的冪陣列。

🔑 Takeaways#

• Pattern: 排序 + 相向雙指針 + 組合計數
• 關鍵技巧: 排序後固定最小值用 Two Pointers 找最大可選範圍；中間元素的選擇是獨立的二元決策，所以貢獻 2^(right-left)；預計算取模冪次避免溢位