# 1593. Split a String Into the Max Number of Unique Substrings
###### tags: `Leetcode` `Medium` `backtracking` `DFS`
Link: https://leetcode.com/problems/split-a-string-into-the-max-number-of-unique-substrings/
## 思路
一开始的想法是用greedy做(start adding substrings of length 1, if we're not able to add, try to add substring of length 2 and so on)
但是
- Example 1. this example "ababab" greedily the ans will be 3 but expected output is 4 ["ab", "a", "ba", "b"]
- Example 2. "aaabacaa" answer:["aaa", "b", "a", "c", "aa"] but there isn't any simple greedy approach that can figure out that the first aaa it sees must be grouped together.

所以枚举所有解
## Code

class Solution {
    int maxSplit = 0;
    public int maxUniqueSplit(String s) {
        dfs(s, 0, new HashSet<>());
        return maxSplit;
    }
    private void dfs(String s, int start, Set<String> subStr){
        if(start==s.length()){
            maxSplit = Math.max(maxSplit, subStr.size());
        }
        for(int i=start; i<s.length(); i++){
            String sub = s.substring(start, i+1);
            if(subStr.contains(sub)) continue;
            subStr.add(sub);
            dfs(s, i+1, subStr);
            subStr.remove(sub);
        }
    }
}