Get all valid permutations of l pairs of (), m pairs of [] and n pairs of {}.

Assumptions

• l, m, n > = 0

Examples

l = 1, m = 1, n = 0, all the valid permutations are ["()[]", "([])", "[()]", "[]()"]

Solution: 每层recursion, 左括号只要remain > 0就可以加，右括号需要用stack来记录左括号，当栈顶元素为配对的左括号时，可以加右括号，同时把栈顶弹出。注意backtracking。注意用array简化参数和输入。

  private final char[] bracket = {'(', ')', '[', ']', '{', '}'};
  public List<String> validParentheses(int l, int m, int n) {
    int num = (l + m + n) * 2;
    List<String> ans = new ArrayList<>();
    int[] remain = {l, l, m, m, n, n};
    helper(new StringBuilder(), ans, remain, new LinkedList<Character>(), num);
    return ans;
  }
  private void helper(StringBuilder path, List<String> ans, int[] remain, LinkedList<Character> stack, int num) {
    if (path.length() == num) {
      ans.add(path.toString());
    }
    for (int i = 0; i < remain.length; i++) {
      if (i % 2 == 0) {
        if (remain[i] > 0) {
          path.append(bracket[i]);
          remain[i]--;
          stack.offerLast(bracket[i]);
          helper(path, ans, remain, stack, num);
          remain[i]++;
          path.deleteCharAt(path.length() - 1);
          stack.pollLast();
        }
      } else {
        if (!stack.isEmpty() && stack.peekLast() == bracket[i - 1]) {
          path.append(bracket[i]);
          remain[i]--;
          stack.pollLast();
          helper(path, ans, remain, stack, num);
          remain[i]++;
          path.deleteCharAt(path.length() - 1);
          stack.offerLast(bracket[i - 1]);
        }
      }
    }
  }

wrong and bad: 因为要配对，所以不能只根据个数来加右括号

  int l, m, n;
  public List<String> validParentheses(int l, int m, int n) {
    List<String> ans = new ArrayList<>();
    int[] param = new int[6];
    this.l = l;
    this.m = m;
    this.n = n;
    helper(new StringBuilder(), ans, param);
    return ans;
  }
  private void helper(StringBuilder path, List<String> ans, int[] param) {
    if (path.length() == (l + m + n) * 2) {
      ans.add(path.toString());
    }
    if (param[0] < l) {
      add_delete('(', 0, param, path, ans);
    }
    if (param[2] < m) {
      add_delete('[', 2, param, path, ans);
    }
    if (param[4] < n) {
      add_delete('{', 4, param, path, ans);
    }
    if (param[1] < param[0] && path.charAt(path.length() - 1) != '[' && path.charAt(path.length() - 1) != '{') {
      add_delete(')', 1, param, path, ans);
    }
    if (param[3] < param[2] && path.charAt(path.length() - 1) != '(' && path.charAt(path.length() - 1) != '{') {
      add_delete(']', 3, param, path, ans);
    }
    if (param[5] < param[4] && path.charAt(path.length() - 1) != '(' && path.charAt(path.length() - 1) != '[') {
      add_delete('}', 5, param, path, ans);
    }
  }
  private void add_delete(char c, int i, int[] param, StringBuilder path, List<String> ans) {
    path.append(c);
    param[i]++;
    helper(path, ans, param);
    param[i]--;
    path.deleteCharAt(path.length() - 1);
  }