题目重点：将符号选择转为连续整数子集和，按大绝对值优先取负，解释可行性与最小字典序证明。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 每个绝对值 1..n 恰好出现一次，输出可自行重排；按升序排列的数组比较字典序。
- 不可行时示例返回 None，正式接口的失败标记未公开，现场需核对。
- n≥0，目标为整数；不允许重复绝对值或仅取部分数字。
解题路线
- 先全取正，和 S=n(n+1)/2。把某个 v 改负会减少 2v，因此负数绝对值集合必须求和 R=(S−target)/2。|target|>S 或奇偶不符立即无解。
- 集合 {1..n} 能组成从 0 到 S 的每个整数和，可归纳证明：加入 n 后区间 [0,S_{n−1}] 与 [n,n+S_{n−1}] 相接或重叠。因此通过范围和奇偶检查就足够。
- 从 v=n 降到 1，若 v≤R 就取 −v 并减少 R，否则取正。为什么不担心后续无法补齐？选择 v 后 R−v≤S_{v−1}；跳过 v 时 R<v，而 v≥2 时 v−1≤S_{v−1}，剩余仍可行。
- 字典序证明：更大绝对值的负数排在更前。只要取 −v 可完成目标，任何不取 −v 的可行解在已固定更大值之后都更大。最后输出负值按绝对值降序、正值升序。
手动走一遍
n=4,target=0，S=10、R=5。先取 −4，R=1；跳过 3、2，取 −1，输出 [-4,-1,2,3]。target=1 因 S−target 为奇数无解；target=10 则全部正数。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def smallest_signed_permutation(n: int, target: int) -> list[int] | None:
if n < 0:
raise ValueError("n must be nonnegative")
total = n * (n + 1) // 2
if abs(target) > total or (total - target) % 2:
return None
remaining = (total - target) // 2
negative = set()
for value in range(n, 0, -1):
if value <= remaining:
negative.add(value)
remaining -= value
assert remaining == 0
return [-value for value in range(n, 0, -1) if value in negative] + [
value for value in range(1, n + 1) if value not in negative
]
复杂度
O(n) 时间、O(n) 输出与集合空间。独立验证枚举全部符号组合，按目标和选择最小排序数组，覆盖 n=0..8 的 285 个目标查询，包括越界与奇偶失败。
易错点与追问
容易失分的边界
- 误把目标和直接当负数子集和。
- 负数按绝对值升序输出，破坏字典序。
- 做指数 DFS 后归咎递归深度，未利用连续值域。
- 任意权重集合不一定能表示连续和，不能迁移此贪心。
继续深挖
- 若数字变成任意正整数，什么地方需要子集和 DP？
- 要求保留原始下标顺序时字典序决策如何改变？
- 若输出无解必须空数组，如何与 n=0 合法解区分？
