Least Signed Permutation with a Target Sum

### Problem Given a positive integer `n` and an integer `target`, return the lexicographically smallest integer array of length `n` satisfying both conditions: - Its elements sum to `target`. - Their absolute values form a permutation of `1,2,...,n`. Each magnitude must therefore appear exactly once, with either a positive or a negative sign. Array order is not fixed. Return an empty array if no valid array exists. Lexicographic order compares the first differing elements using ordinary integer order. ```cpp class Solution { public: vector<int> lexSmallestNegatedPerm(int n, long long target); }; ``` ### Examples **Example 1:** ```text Input: n = 4, target = 0 Output: [-4,-1,2,3] Explanation: The absolute values are exactly 1,2,3,4 and the sum is zero. No valid array is lexicographically smaller. For example, the other sign choice [-3,-2,1,4] also sums to zero but is larger. ``` **Example 2:** ```text Input: n = 4, target = 1 Output: [] Explanation: No assignment of signs to the magnitudes 1,2,3,4 has sum one, regardless of their order. ``` ### Constraints - `1 <= n <= 100000`. - `-10000000000 <= target <= 10000000000`. ### Clarifying Questions - May zero appear? No; every absolute value must be in `1..n`. - May a magnitude be omitted or repeated with another sign? No; each is used once. - Is element order part of the choice? Yes; return the lexicographically smallest full array. - Can `target` be negative or zero? Yes. - Must the original `long long target` parameter be retained? Yes; its permitted range exceeds 32-bit signed integers. ### What a Strong Answer Covers - Exact magnitude usage, the target sum, and lexicographic minimality together. - A valid construction or a complete impossibility argument. - Negative and zero targets, endpoint cases, and a single magnitude. - Numeric safety and resources for the full input and output sizes. ### Follow-up Questions - How would requiring the magnitudes in their original increasing order change the permitted outputs? - How could requesting every valid array affect the output size? ```hint Relate sign changes to the requested sum Start from the sum S of all positive magnitudes. Negating x lowers that sum by 2*x. After the range and parity feasibility checks, choose which magnitudes supply the required reduction, preferring larger magnitudes to receive negative signs when a completion remains possible. Arrange the selected signed integers in increasing order. ```