public String findContestMatch(int n) {
StringBuilder sb = new StringBuilder();
helper(sb, 3, n, 1);
return sb.toString();
}
void helper(StringBuilder sb, int sum, int n, int val) {
if (sum > n + 1) {
sb.append(val);
return;
}
sb.append('(');
helper(sb, (sum << 1)  1, n, val);
sb.append(',');
helper(sb, (sum << 1)  1, n, sum  val);
sb.append(')');
}
3 ms Java Recursive clean code


The basic idea is to build a tree, for the case of
n = 8
, the tree is like this:
I had the similar idea and below is my code:
public class Solution { public String findContestMatch(int n) { TreeNode[] matches = new TreeNode[n]; for (int i = 0; i < n; i++) { matches[i] = new TreeNode(i + 1); } int len = n; while (len > 1) { for (int i = 0; i < len / 2; i++) { TreeNode newNode = new TreeNode(matches[i].val); newNode.left = matches[i]; newNode.right = matches[len  1  i]; matches[i] = newNode; } len = len >> 1; } StringBuilder sb = new StringBuilder(); dfs(matches[0], sb); return sb.toString(); } void dfs(TreeNode root, StringBuilder sb) { if (root.left == null && root.right == null) { sb.append(root.val); return; } sb.append("("); dfs(root.left, sb); sb.append(","); dfs(root.right, sb); sb.append(")"); } }
It's verbose but easier to understand: just build the tree by grouping matches one round at a time, then do a DFS to get the output string.
My solution's complexity:
 for building the tree:
2N
space and2N
time.  for DFS:
2N
time.
While his solutions uses
2N
time andO(1)
space. It's also much conciser than mine.I tried to submit his solution, got a 4ms (99%) while my own solution is 6ms (98%) (20170720 16:58:23);
I still decided to share my version since mine is easier to understand and come up with step by step. But again I definitely think his is better.
 for building the tree: