22. Generate Parentheses

source: https://leetcode.com/problems/generate-parentheses/

Question

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

思路

这题可以用回溯法去做。但是要筛选掉以)结尾，但是)数量大于(.

var generateParenthesis = function (n) {
  const ret = [];
  const nums = [...Array(n).fill("("), ...Array(n).fill(")")];
  const backtrack = (track, is) => {
    if (track.length === nums.length) {
      const v = track.join("");
      if (!ret.includes(v)) ret.push(v);
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (is.includes(i)) continue;
      if (
        nums[i] === ")" &&
        track.filter((v) => v === ")").length + 1 >
          track.filter((v) => v === "(").length
      )
        break;
      track.push(nums[i]);
      backtrack(track, [...is, i]);
      track.pop();
    }
  };
  backtrack([], []);
  return ret;
};

End

对于回溯法的模版要熟练。