# Java DFS solution, use one optimization

• First calculate the minimum number of steps to get the answer. The method fellows https://leetcode.com/discuss/68327/java-dfs-solution-with-optimizations.

Then enumerate all the possible states and save the results. Pay attention, we should remove the duplicate results.

``````public class Solution {
List<String> res = new ArrayList<>();
Set<String> hash = new HashSet<>();
Stack<Character> stack = new Stack<>();
int n, ans;
public void search(String s, int p, String s1, int sum) {
if (sum > ans)
return;
if (n == p) {
if (stack.size() == 0)
return;
}
char c = s.charAt(p);
if (c != '(' && c != ')')
search(s, p+1, s1+c, sum);
else {
char d = '0';
if (stack.isEmpty())
stack.push(c);
else {
if (c == stack.peek() || c == '(')
stack.push(c);
else d = stack.pop();
}
search(s, p+1, s1+c, sum);
if (d != '0')
stack.push(d);
else stack.pop();
search(s, p+1, s1, sum+1);
}
}
public List<String> removeInvalidParentheses(String s) {
this.n = s.length();
ans = 0;
int leftCnt = 0;
for(int i = 0; i < n; i++) {
if(leftCnt>0 && s.charAt(i)==')') {
ans--;
leftCnt--;
}
else if(s.charAt(i)==')')
ans++;
else if(s.charAt(i)=='(') {
ans++;
leftCnt++;
}
}
search(s, 0, "", 0);