Find a lesson, question or project

Start typing to search published content and planned structures.

↑ ↓ moveEnter openEsc close

Permutations III in Java: Alternate Odd and Even with Backtracking

Learn parity-constrained permutations with simple reasoning, commented Java, a recursion tree and dry runs showing choices, returns and undo.

MediumRecursion and backtrackingPattern: recursion, backtracking

Problem statement

Given an integer n, arrange every number from 1 through n exactly once. Return every arrangement in which neighbors alternate between odd and even, in lexicographic order.

The original Permutations III prompt on takeUforward uses 1 ≤ n ≤ 10. You can practise Permutations III on LeetCode.

For n=3, the answer is [[1,2,3], [3,2,1]]. For n=2, it is [[1,2], [2,1]]. For n=1, it is [[1]].

“Alternating” means odd/even, not smaller/larger. [3,2,1] is valid despite decreasing throughout. [1,3,2] is invalid because 1 and 3 are both odd.

This is not Permutations II, where duplicate input values require special handling. Here the input is one integer, and all values 1..n are distinct.

Constraints & requirements

CONTRACT
Different parity means odd/even, not increasing/decreasing. Return the actual permutations, not only their count.

Examples 3 test cases

  1. Example 1 Case 1

    Input
    n=3
    Output
    [[1, 2, 3], [3, 2, 1]]

    An odd-sized input must start and end with odd numbers.

  2. Example 2 Case 2

    Input
    n=1
    Output
    [[1]]

    There is no adjacent pair to violate the rule.

  3. Example 3 Case 3

    Input
    n=4
    Output
    [[1,2,3,4], [1,4,3,2], [2,1,4,3], [2,3,4,1], [3,2,1,4], [3,4,1,2], [4,1,2,3], [4,3,2,1]]

    Either starting parity works; ascending choices produce dictionary order.

Solve on LeetCode ↗

Hints Optional

Hints become more specific one step at a time.
01Check one new pair

When you append a number, only the pair with the last chosen number is new. Can you reject an invalid pair immediately?

02Remember what is available

Use a path for the order and a used array to prevent repeating a number. A complete length-n path must be saved as a copy.

03Restore and keep order

Try candidates from 1 to n. Choose, recurse, then undo both the path and used flag. For odd n, one extra odd number forces an odd first choice.

How to think before coding

The answer is a permutation, so every number can appear once, in any position. Keep a used flag per number and a path. A candidate is legal only when unused and opposite in parity to the path’s last number. At length n, copy the path. Remove the last number AND clear its flag after returning. For odd n, only an odd starting value can use the extra odd number.

Brute force: generate everything, then filter

Generate all n! permutations using a path and used array. At each full permutation, scan its adjacent pairs. Save only those whose neighboring remainders modulo two differ.

This works, but notices invalidity late. For example, [1,3] can never become valid: the first pair is already odd/odd, regardless of what follows. Generating its descendants is wasted work.

Java
public static List<List<Integer>> permuteBrute(int n) {
    List<List<Integer>> answer = new ArrayList<>(); // Retain only valid complete permutations.
    buildAllPermutations(n, new ArrayList<>(), new boolean[n + 1], answer); // Initially all values are free.
    return answer; // Ascending candidate choices already order the accepted outputs.
}

private static void buildAllPermutations(int n, List<Integer> path,
                                         boolean[] used, List<List<Integer>> answer) {
    if (path.size() == n) { // Brute force delays parity checks until every position is filled.
        for (int i = 1; i < n; i++) { // The first adjacent pair ends at index one.
            if (path.get(i - 1) % 2 == path.get(i) % 2) return; // Reject the whole permutation.
        }
        answer.add(new ArrayList<>(path)); // Later backtracking must not mutate this saved result.
        return; // There are no remaining positions to fill.
    }
    for (int candidate = 1; candidate <= n; candidate++) { // Try the smallest next value first.
        if (used[candidate]) continue; // Each integer may appear only once in a permutation.
        used[candidate] = true; // Reserve this value for the current branch.
        path.add(candidate); // Record its position, even if the prefix has invalid parity.
        buildAllPermutations(n, path, used, answer); // Generate every completion before filtering.
        path.remove(path.size() - 1); // Restore the parent prefix after the child returns.
        used[candidate] = false; // The next sibling must be allowed to choose this value again.
    }
}

For n=4 this makes 65 recursive calls, including the empty root, and constructs 24 complete permutations. Only 8 are valid.

Intuition: build an answer one position at a time

Imagine placing numbered tiles in a row. Once [1,2] is on the table, the next tile must be odd. Tile 1 is already used, so for n=3 only tile 3 is available.

Two separate questions decide whether a choice is legal:

  1. Availability: have we used this number in this branch?
  2. Parity: is it different from the last number’s parity?

If both checks pass, place it, ask recursion to finish the row, and remove it afterward. Removing it lets the next possible choice start from the same original prefix. That is backtracking: choose → explore → undo.

The recursive promise is: “Given this valid prefix and its used numbers, append every valid completion to the answer.” Each child fills one more position, so a length-n prefix is the base case.

Why an odd-sized input must start with an odd number

For n=3, the inventory is odd={1,3} and even={2}. There are two possible parity patterns:

Worked example · read from top to bottom
odd → even → odd     uses 2 odds, 1 even: possible
even → odd → even    needs 2 evens: impossible

More generally, n=2m+1 supplies m+1 odds and m evens. Only an odd-start pattern has enough odd positions. It also ends with odd.

For n=2m, both groups contain m values, so either starting parity works. For n=4, [2,1,4,3] is valid: do not reject all even first choices.

Skipping an even root choice when n is odd is an extra pruning step. Without it, a parity-checking algorithm remains correct, but explores some branches that cannot finish.

Better solution: reject an invalid prefix immediately

Your local practice/PermutationN.java uses this same choose/mark/recurse/undo structure, iterating 1 through n directly instead of constructing an input array. The article also rejects an even first choice when n is odd: there are more odd values, so only an odd-start alternating sequence can fill all positions. Indexed list access below keeps the example compatible with Java 17 rather than requiring Java 21’s getLast()/removeLast().

Maintain two shared objects:

  • path: the chosen numbers in their current order.
  • used[value]: whether that value is already in this path.

Modulo two gives a number’s parity: even % 2 is 0, odd % 2 is 1. Equal remainders mean the pair is forbidden. Check this before creating the child call.

Java
public static List<List<Integer>> permute(int n) {
    List<List<Integer>> answer = new ArrayList<>(); // Each saved list will be a separate object.
    boolean[] used = new boolean[n + 1]; // Index zero is unused because the values are 1 through n.
    buildAlternating(n, new ArrayList<>(), used, answer); // Begin with no chosen numbers.
    return answer; // DFS with ascending candidates gives lexicographic order without sorting.
}

private static void buildAlternating(int n, List<Integer> path,
                                     boolean[] used, List<List<Integer>> answer) {
    if (path.size() == n) { // A valid prefix has now used every required number.
        answer.add(new ArrayList<>(path)); // Copy: the shared path will shrink on return.
        return; // Stop this branch; a permutation cannot contain more than n values.
    }
    for (int candidate = 1; candidate <= n; candidate++) { // Smaller next values come first.
        if (used[candidate]) continue; // Do not repeat a number already in this branch.
        if (!path.isEmpty() && path.get(path.size() - 1) % 2 == candidate % 2) {
            continue; // Equal remainders mean odd/odd or even/even: reject before recursing.
        }
        if (path.isEmpty() && n % 2 == 1 && candidate % 2 == 0) {
            continue; // Odd n has one extra odd number, so only odd-start patterns can finish.
        }
        used[candidate] = true; // Make this number unavailable while the child explores.
        path.add(candidate); // Extend the valid prefix by exactly one value.
        buildAlternating(n, path, used, answer); // Ask the child to fill the remaining positions.
        path.remove(path.size() - 1); // The child has returned; undo our own appended value.
        used[candidate] = false; // Restore availability for the next candidate and parent.
    }
}

These methods assume the stated 1..10 input range. Import java.util.* and place them inside your class. For a judge that supplies Solution, use that class name and its permute(int n) entry point. The downloadable teaching class and the practice pane’s Main driver are separate conveniences, not part of the problem’s input.

Recursion tree for n=3

Every displayed node below represents an actual recursive call. A skipped choice creates no child frame.

Worked example · read from top to bottom
fill([])
├─ choose 1 → fill([1])
│  ├─ try 1: already used → no call
│  ├─ choose 2 → fill([1,2])
│  │  └─ choose 3 → fill([1,2,3]) → save a copy; return
│  │     parent undoes 3, then returns
│  └─ try 3: same parity as 1 → no call
│     root undoes 1 after this child returns
├─ try 2: even start cannot finish odd n → no call
└─ choose 3 → fill([3])
   └─ choose 2 → fill([3,2])
      └─ choose 1 → fill([3,2,1]) → save a copy; return

Already-used attempts are omitted from this diagram for readability. At each Java loop iteration, test used[num] first; only an allowed candidate creates a child.

Dry run: the call stack is not the path

Numbered illustrated dry run for Permutations III; the text transcript explains the states.
Follow the numbered panels in order. Open full-size dry run ↗
Read the text transcript

The path holds chosen numbers. The call stack holds active and waiting function frames. For n=3, immediately before saving the first answer:

Worked example · read from top to bottom
TOP    fill([1,2,3])  active: save, then return
       fill([1,2])    waiting: undo its choice 3
       fill([1])      waiting: undo its choice 2
BOTTOM fill([])       waiting: undo its choice 1

The labels identify the prefix at each call’s entry. All frames refer to the same mutable path; the deeper call has temporarily extended it. Each waiting frame retains its own loop candidate and return position.

Event Shared path Live frames Saved answers
Root starts [] 1 []
Choose 1; child enters [1] 2 []
Choose 2; child enters [1,2] 3 []
Choose 3; child enters [1,2,3] 4 []
Save a copy [1,2,3] 4 [[1,2,3]]
Leaf returns and is popped [1,2,3] 3 unchanged
Resumed parent undoes 3 [1,2] 3 unchanged
After returning and undoing 2 [1] 2 unchanged

Returning does not automatically remove a value from an ArrayList. The child frame pops first; the resumed parent then executes its explicit undo statements. In a dry run, record return, path.remove(...) and used[num]=false as distinct actions.

Questions that usually cause confusion

Why check only the last number, not the whole path?

Before this choice, every old neighboring pair is already valid. Appending one number creates exactly one new pair: last + candidate. If that pair passes, the new prefix remains valid. Rechecking the earlier pairs does no useful work.

Why use both path and used?

They answer different questions: path records position; used records availability. Checking path.contains(candidate) would also work, but scans up to n values each time. The boolean lookup is constant time. Index zero is unused, so n+1 slots let us index directly by number.

Why undo both changes?

Removing the last value restores the order. Clearing used restores availability. Forgetting either leaves the next sibling with corrupted state. For example, after finishing the branch starting with 1, other branches must be able to use 1 again.

Why must we save a copy?

answer.add(path) stores the same list object repeatedly. Later removes would alter every reference to it, and after the search the path is empty. new ArrayList<>(path) makes a snapshot that survives all later backtracking.

Why remove by the last index rather than by value?

This frame appended exactly one value at the end. Removing that position precisely undoes its action. In Java, remove(int) means index; remove(Integer) means value. Using candidate as the index would remove the wrong position or throw an exception.

Why not use the index-increasing subset pattern?

A permutation cares about order. After choosing 3, we may still need 2 or 1. Starting the next loop only after 3 would miss [3,2,1]. Scan all values at each depth and let used flags exclude repetitions. Compare the different promise in Subsets in Java.

Why is the answer already in lexicographic order?

Compare two outputs at their first different position. The search tries the smaller value there first and finishes all its descendants before trying the larger value. Rejecting illegal choices removes branches but never changes their relative order. No final sort or Set is necessary.

For n=4 the output is:

Worked example · read from top to bottom
[1,2,3,4]  [1,4,3,2]  [2,1,4,3]  [2,3,4,1]
[3,2,1,4]  [3,4,1,2]  [4,1,2,3]  [4,3,2,1]

Does n=1 need a special rule?

No. Choose 1, reach the base case, and save [1]. There is no neighboring pair to reject. The empty starting path is a partial state, not a requested output for this problem.

Why this algorithm is correct

At entry, the path contains distinct values and every neighboring pair has different parity. The used flags identify exactly those path values. The checks maintain this invariant when a candidate is added.

At length n, a valid path contains all n allowed numbers once, so every saved result meets the contract. For any valid final permutation, each successive value is unused and has legal parity. Its first value also passes the odd-n rule, so the search can follow that exact route. Thus no valid permutation is missed.

Different routes have a first different chosen value, so cannot produce the same final list. Ascending branch order guarantees the required output order. Finally, undo restores the invariant for the next sibling.

Complexity and a useful count check

Let A be the number of valid answers and C the number of recursive prefix calls, including the root. Each non-leaf tries n candidates; saving each answer copies n numbers. The time is O(n·C + n·A). A simple worst-case upper bound is O(n·n!), not a claim that pruning does no good.

For n=4, valid-prefix backtracking visits 29 calls rather than brute force’s 65, and produces 8 full candidates rather than 24. It avoids invalid descendants, but still has to write every requested result.

The path, used array, and deepest live stack need O(n) auxiliary space. The returned lists occupy Θ(n·A) output space, separately. With a full path, there are n+1 live helper frames including the empty root—not n! simultaneous frames.

We can count the answers independently, without listing them:

  • For n=2m: two starting parity patterns, with m! orders for each group, giving A=2·(m!)².
  • For n=2m+1: only the odd-start pattern, giving A=(m+1)!·m!.

Here factorial means all possible orders: 3!=3×2×1. Thus n=3 gives 2, n=4 gives 8, and n=10 gives 28,800 answers. Counting with a formula does not solve the task of returning those lists; even an ideal generator needs Ω(n·A) time to write them.

Look for “return every arrangement,” “use each number once,” and a local adjacency rule. This suggests permutation backtracking with early rejection. Binary strings without consecutive ones uses a similar local-rule idea, while Palindrome Permutation II tracks a repeated-letter inventory instead of distinct values.

  • Do not confuse odd/even alternation with alternating increases and decreases.
  • Do not force an odd first value when n is even.
  • Do not sort each individual result: that destroys the permutation and can break adjacency.
  • Do not return only the factorial count when lists are requested.
  • Check output length, distinctness, parity, lexicographic order, and independent saved copies—not just the number of outputs.

Company research note

No dated, attributable public candidate report for this exact parity-constrained problem was verified on 4 October 2026. Similarly named alternating-order questions and broad company lists are not evidence for a company badge. No company tag is assigned here.

Final takeaway

Choose an unused number with the opposite parity. Let the child finish the row. Then restore both the row and availability. Small-first choices give ordered answers; copied lists keep those answers safe.

Download the tested Java solutions. The teaching methods use Java 17+. The dry run follows the same tested choose/recurse/undo operations as the published method.

Practice next

Next lessonGenerate Binary Strings Without Consecutive Ones

Compare another local adjacency rule that prunes invalid prefixes.

Back to Recursion and backtracking →