# 544. Output Contest Matches

## Approach 1: Recursive

• Time: $O(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 class Solution { public: string findContestMatch(int n) { vector matches(n); for (int i = 0; i < n; ++i) matches[i] = to_string(i + 1); return generateMatches(matches); } private: string generateMatches(const vector& matches) { if (matches.size() == 1) return matches[0]; vector nextMatches; for (int i = 0; i < matches.size() / 2; ++i) nextMatches.push_back("(" + matches[i] + "," + matches[matches.size() - 1 - i] + ")"); return generateMatches(nextMatches); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public String findContestMatch(int n) { List matches = new ArrayList<>(); for (int i = 1; i <= n; ++i) matches.add(String.valueOf(i)); return generateMatches(matches); } private String generateMatches(List matches) { if (matches.size() == 1) return matches.get(0); List nextMatches = new ArrayList<>(); for (int i = 0; i < matches.size() / 2; ++i) nextMatches.add("(" + matches.get(i) + "," + matches.get(matches.size() - 1 - i) + ")"); return generateMatches(nextMatches); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution: def findContestMatch(self, n: int) -> str: def generateMatches(matches: List[str]) -> str: if len(matches) == 1: return matches[0] nextMatches = [] for i in range(len(matches) // 2): nextMatches.append( '(' + matches[i] + ',' + matches[len(matches) - 1 - i] + ')') return generateMatches(nextMatches) return generateMatches([str(i + 1) for i in range(n)]) 

## Approach 2: Iterative

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public: string findContestMatch(int n) { vector matches(n); for (int i = 0; i < n; ++i) matches[i] = to_string(i + 1); while (n > 1) { for (int i = 0; i < n / 2; ++i) matches[i] = "(" + matches[i] + "," + matches[n - 1 - i] + ")"; n /= 2; } return matches[0]; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution { public String findContestMatch(int n) { String[] matches = new String[n]; for (int i = 0; i < n; ++i) matches[i] = String.valueOf(i + 1); while (n > 1) { for (int i = 0; i < n / 2; ++i) matches[i] = "(" + matches[i] + "," + matches[n - 1 - i] + ")"; n /= 2; } return matches[0]; } } 
  1 2 3 4 5 6 7 8 9 10 class Solution: def findContestMatch(self, n: int) -> str: matches = [str(i + 1) for i in range(n)] while n > 1: for i in range(n // 2): matches[i] = '(' + matches[i] + ',' + matches[n - 1 - i] + ')' n //= 2 return matches[0]