Lexicographically Smallest Negated Permutation that Sums to Target - Solution & Explanation

Problem Overview: You start with a permutation [1,2,3,...,n]. You may negate any elements (turn x into -x). The goal is to make the total sum equal to a given target while producing the lexicographically smallest resulting array.

The original sum of the permutation is S = n(n+1)/2. Negating a value x changes the total sum by -2x. If the final target is T, the total reduction needed is D = S - T. That means the values you negate must sum to D/2. The problem reduces to selecting numbers from 1..n whose sum equals D/2, while ensuring the final signed permutation is lexicographically smallest.

Approach 1: Brute Force Subset Enumeration (Exponential Time)

Enumerate every subset of numbers from 1..n and treat each subset as the elements to negate. For each subset, compute the resulting array and check whether the total equals the target. Among all valid permutations, choose the lexicographically smallest. This directly models the problem but requires checking up to 2^n subsets. Time complexity is O(2^n * n) and space complexity is O(n). Useful only for reasoning about correctness on very small inputs.

Approach 2: Dynamic Programming Subset Sum (O(n * K))

Compute K = (S - T) / 2. The task becomes a classic subset-sum problem: select numbers that sum to K. A DP table can track which sums are reachable using numbers 1..n. After computing feasible sums, reconstruct a subset that prioritizes smaller indices so the resulting signed permutation becomes lexicographically smaller. Time complexity is O(n * K) with space O(K). Works but becomes expensive when K is large.

Approach 3: Greedy Construction (Optimal, O(n))

Use a greedy strategy based on lexicographic priority. Compute K = (S - T)/2. Iterate from i = 1 to n. For each value, try negating it (which contributes i toward the subset sum). Only commit if the remaining sum K - i can still be formed using the remaining numbers. Because the remaining values form a continuous range, feasibility can be checked with simple math bounds instead of full DP. This keeps the prefix as negative as possible, making the array lexicographically smallest.

This greedy works because earlier indices dominate lexicographic order. If negating i still allows a valid completion, doing so always produces a smaller prefix. Time complexity is O(n) and space complexity is O(1).

Recommended for interviews: The greedy math approach. Interviewers expect you to recognize the transformation from sum adjustment to subset sum and then exploit the consecutive structure of 1..n. Brute force or DP shows understanding, but the greedy solution demonstrates stronger algorithmic insight using greedy, math, and array reasoning.