BFS DFS recursive & DFS iterative


  • 1
            // BFS 9ms
    	public List<List<Integer>> combineBFS(int n, int k) {
    		List<List<Integer>> result = new ArrayList<>();
    		if (k == 0) {
    			result.add(new ArrayList<>());
    			return result;
    		}
    		for (int i = 1; i <= n - k + 1; i++) {
    			List<Integer> list = new ArrayList<>();
    			list.add(i);
    			result.add(list);
    		}
    		for (int m = 1; m < k; m++) {
    			int size = result.size();
    			for (int i = 0; i < size; i++) {
    				List<Integer> list = result.get(i);
    				int maxNum = list.get(list.size() - 1);
    				int maxNumNextSize = n - k + list.size() + 1;
    				for (int j = maxNum + 1; j < maxNumNextSize; j++) {
    					List<Integer> newList = new ArrayList<>(list);
    					newList.add(j);
    					result.add(newList);
    				}
    				list.add(maxNumNextSize);
    			}
    		}
    		return result;
    	}
    	
    	// DFS 12ms
    	public List<List<Integer>> combineDFS(int n, int k) {
    		List<List<Integer>> result = new ArrayList<>();
    		List<Integer> list = new ArrayList<>();
    		if (k == 0) {
    		    result.add(list);
    		    return result;
    		}
    		if (n == 0) {
    		    return result;
    		}
    		list.add(1);
    		while (list.size() >= 1) {
    			int size = list.size();
    			int maxNum = list.get(size - 1);
    			if (size == k) {
    				result.add(new ArrayList<>(list));
    				while (maxNum < n) {
    					maxNum++;
    					list.remove(k - 1);
    					list.add(maxNum);
    					result.add(new ArrayList<>(list));
    				}
    				while (size > 0) {
    					maxNum = list.get(size - 1);
    					if (maxNum == n - k + size) {
    						list.remove(size - 1);
    						size = list.size();
    					} else {
    						list.remove(size - 1);
    						list.add(maxNum + 1);
    						break;
    					}
    				}
    			} else {
    				list.add(maxNum + 1);
    			}
    		}
    		return result;
    	}
    	// DFS Recursive 4ms
    	List<List<Integer>> res;
    	public List<List<Integer>> combineDFSRec(int n, int k) {
    		res = new ArrayList<>();
    		if (k == 0) {
    			res.add(new ArrayList<>());
    			return res;
    		}
    		if (n == 0) {
    			return res;
    		}
    		helper(new ArrayList<>(), n, k, 0);
    		return res;
    	}
    
    	public void helper(List<Integer> list, int n, int k, int maxNum) {
    		if (list.size() == k) {
    			res.add(new ArrayList<>(list));
    			return;
    		}
    		int maxNumNextSize = n - k + list.size() + 1;
    		for (int i = maxNum + 1; i <= maxNumNextSize; i++) {
    			list.add(i);
    			helper(list, n, k, i);
    			list.remove(list.size() - 1);
    		}
    	}
    

Log in to reply
 

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