# My easily understandable dfs solution

• the logic is using a counter c to indicate if the Parentheses is valid .

if current char is ')' and c != 0 we need to find if the maximum Parentheses include the current char or not , the same logic could be also applied when current char is '('

the key logic is including or not

``````public List<String> removeInvalidParentheses(String s) {
List<String> rst = new ArrayList<> ();
if (s == null || s.length() == 0) {
return rst ;
}
HashMap<Integer,Set<String>> map = new HashMap<> ();
int min = findMin (0,0, s, 0, "", map);
return new ArrayList<String> (map.get(min)) ;
}

public int findMin (int index, int c, String exp, int rm, String cur, HashMap<Integer, Set<String>> map){
if (index >= exp.length() && c == 0) {
Set<String> set = map.containsKey(rm) ? map.get(rm) : new HashSet<String> ();
map.put(rm, set) ;
return rm ;
}
if(index >= exp.length()) {
return Integer.MAX_VALUE ;
}
if (exp.charAt(index) == ')') {
if (c == 0) {
return findMin(index + 1, c, exp, rm + 1, cur, map);
} else {
return Math.min(findMin(index + 1, c ,exp, rm + 1, cur, map), findMin(index + 1, c - 1 ,exp, rm, cur + ")", map)) ;
}
} else if (exp.charAt(index) == '(') {
return Math.min(findMin(index + 1, c, exp, rm + 1, cur, map), findMin(index + 1, c + 1 , exp, rm, cur + "(", map));
} else {
return findMin (index + 1, c, exp, rm, cur + exp.charAt(index), map) ;
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.