Return all Numbers lesser than maximum number - Google interview

http://www.1point3acres.com/bbs/thread-205789-1-1.html
给一个list的digit，给一个maximum number，要求返回所有由这些digit组成的且不超过max的数字，一个digit可以重复使用比如{3,7,8}, max=1000, 返回{3,33,333,37,38...7,738,...}
突然想到我明明问了她0不能放在第一位的，结果写的时候给忘了...orz
然后写完跑了几个test case，并且跑完她问我有没有可以优化的，我说可以对list排序一下，这样遇到大于max的可以直接返回，不用考虑后序结果
写的时候也忘记考虑有重复数字了。。。orz.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
最后又问了复杂度，一开始答O(n^2)，后来觉得不对，改成了O(n!)。【每题必问复杂度。。。

1. void helper(vector<int>& digits, int tmp, int maxNumber, vector<int> &res) {
2.     if (tmp > maxNumber) {
3.         return;
4.     }
5.     if (tmp != 0) {.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
6.         res.push_back(tmp);. Waral 鍗氬鏈夋洿澶氭枃绔�,
7.     }
8.     for (int i = 0; i < digits.size(); i++) {. visit 1point3acres.com for more.
9.         helper(digits, tmp * 10 + digits[i], maxNumber, res);
10.     }
11. }
12. 
    
13. vector<int> getNumbers(vector<int>& digits, int maxNumber) {.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
14.     vector<int> res;
15.     sort(digits.begin(), digits.end());
16.     helper(digits,0, maxNumber, res);
17.     if (digits[0] == 0) {
18.         res.push_back(0);
19.     }
20.     return res;
21. }

public List<String> getNumbers(List<int> digits, int maxNumber) {
        LinkedList<int> result = new LinkedList();. Waral 鍗氬鏈夋洿澶氭枃绔�,
        recursiveGetNumbers(digits, 0, maxNumber, 0, result);
        return result;
}

public void recursiveGetNumbers(List<int> digits, int level, int maxNumber, int curResult, List<int> result) {.1point3acres缃�
        if (level == digits.length) {
                if (curResult <= maxNumber) {
                        result.add(curResult);
                }
                return;
        }
        recursiveGetNumbers(digits, level+1, maxNumber, curResult, result);
        curResult = curResult * 10 + digits[level];
        recursiveGetNumbers(digits, level+1, maxNumber, curResult, result);. 鍥磋鎴戜滑@1point 3 acres
}

X. BFS

1. public List<Integer> getNumbers(int[] digits, int maxNumber) {
2.                 List<Integer> result = new ArrayList<Integer>();
3.                 if(digits.length == 0) return result;
4.                 
5.                 Arrays.sort(digits);
6.                 Queue<Integer> queue = new LinkedList<Integer>();
7.                 queue.add(0);
8.                 
9.                 while(!queue.isEmpty()){
10.                         int size = queue.size();
11.                         for(int i = 0; i < size; i++){.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
12.                                 int previous = queue.poll();
13.                                 for(int j = 0; j < digits.length; j++){
14.                                         int current = previous * 10 + digits[j];
15.                                         if(current <= maxNumber && current != 0){
16.                                                 queue.add(current);
17.                                                 result.add(current);
18.                                         }. from: 1point3acres.com/bbs 
19.                                 }
20.                         }
21.                 }
22.                 
23.                 if(digits[0] == 0) result.add(0, 0); // corner case when there is 0 in digits array
24.                 return result;
25.         }