This assumes you are doing constant amount of work in each call. In general, if you are doing k amount of work(outside calling functions recursively), then time complexity will be O(b^d * k)., O(2^d*k)
Taking the above example, n= 3 pairs. 2^0+2^1+2^2+..........+2^6.
Here b is 2, d is 6 as there are 6 levels.
class Solution {
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
gen(0, 0, "", result, n);
return result;
}
private void gen(int left, int right, String s, List<String> result, int n) {
//termiator
if (left == n && right == n) {
result.add(s);
}
// drill down
if (left < n) {
gen(left + 1, right, s + "(", result, n);
}
if (left > right) {
gen(left, right + 1, s + ")", result, n);
}
}
}
another way, use subtract
class Solution {
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
gen(n, n, "", result);
return result;
}
private void gen(int left, int right, String s, List<String> result) {
//termiator
if (left == 0 && right == 0) {
result.add(s);
return;
}
// drill down
if (left > 0) {
gen(left - 1, right, s + "(", result);
}
if (right > left) {
gen(left, right - 1, s + ")", result);
}
}
}