Skip to content

1718. Construct the Lexicographically Largest Valid Sequence 👍

  • Time: $O(2^n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
 public:
  vector<int> constructDistancedSequence(int n) {
    vector<int> ans(2 * n - 1);
    dfs(n, 0, 0, ans);
    return ans;
  }

 private:
  bool dfs(int n, int i, int mask, vector<int>& ans) {
    if (i == ans.size())
      return true;
    if (ans[i] > 0)
      return dfs(n, i + 1, mask, ans);

    // Greedily fill in `ans` in descending order.
    for (int num = n; num >= 1; --num) {
      if (mask >> num & 1)
        continue;
      if (num == 1) {
        ans[i] = num;
        if (dfs(n, i + 1, mask | 1 << num, ans))
          return true;
        ans[i] = 0;
      } else {  // num in [2, n]
        if (i + num >= ans.size() || ans[i + num] > 0)
          continue;
        ans[i] = num;
        ans[i + num] = num;
        if (dfs(n, i + 1, mask | 1 << num, ans))
          return true;
        ans[i + num] = 0;
        ans[i] = 0;
      }
    }

    return false;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
  public int[] constructDistancedSequence(int n) {
    int[] ans = new int[2 * n - 1];
    dfs(n, 0, 0, ans);
    return ans;
  }

  private boolean dfs(int n, int i, int mask, int[] ans) {
    if (i == ans.length)
      return true;
    if (ans[i] > 0)
      return dfs(n, i + 1, mask, ans);

    // Greedily fill in `ans` in descending order.
    for (int num = n; num >= 1; --num) {
      if ((mask >> num & 1) == 1)
        continue;
      if (num == 1) {
        ans[i] = num;
        if (dfs(n, i + 1, mask | 1 << num, ans))
          return true;
        ans[i] = 0;
      } else { // num in [2, n]
        if (i + num >= ans.length || ans[i + num] > 0)
          continue;
        ans[i] = num;
        ans[i + num] = num;
        if (dfs(n, i + 1, mask | 1 << num, ans))
          return true;
        ans[i + num] = 0;
        ans[i] = 0;
      }
    }

    return false;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
  def constructDistancedSequence(self, n: int) -> list[int]:
    ans = [0] * (2 * n - 1)

    def dfs(i: int, mask: int) -> bool:
      if i == len(ans):
        return True
      if ans[i] > 0:
        return dfs(i + 1, mask)

      # Greedily fill in `ans` in descending order.
      for num in range(n, 0, -1):
        if (mask >> num & 1) == 1:
          continue
        if num == 1:
          ans[i] = num
          if dfs(i + 1, mask | 1 << num):
            return True
          ans[i] = 0
        else:  # num in [2, n]
          if i + num >= len(ans) or ans[i + num] > 0:
            continue
          ans[i] = num
          ans[i + num] = num
          if dfs(i + 1, mask | 1 << num):
            return True
          ans[i + num] = 0
          ans[i] = 0

      return False

    dfs(0, 0)
    return ans