Combination Question and DFS

Most of Combination questions connect to DFS, following structure is common:

private void dfs(int[] nums, int pos, int gap, List<Integer> list, List<List<Integer>> result) {
       
        // 一个合法的解
        if (gap == 0) {
            result.add(new ArrayList<Integer>(list));
            return;
        }
       
        for (int i = pos; i < nums.length; i++) { //扩展状态           
            // 剪枝
            if (gap < nums[i]) {
                return;
            }
           
            list.add(nums[i]); // 扩展动作
            dfs(nums, i, gap-candidates[i], list, result);
            // backtrack 撤销动作
            list.remove(list.size() - 1);
           
        }
    }

Wikipedia上的讲解是：“Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. 
One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible 
along each branch before backtracking.”

深度优先主要思想是：

1. 设置几个方法，有顺序
1. 方法： 1，2，3.....
2. 按照方法1 去执行直到方法一执行不能，尝试方法2
3. 若所有方法都不发执行，退回到上一个步骤执行方法2（因为方法1 已经执行过了）（backtracking)
4. 在执行方法的每一步中要检测是否到达目的地或目标

// recursive  

void dfs()  
{  
    // 判断是否到达终点
    if() {
        return;
    }

    // 尝试每一个可走方向（右下左上） 
    for(i=0; i<n; i++){ 
        // 判断是否可走,可走调用递归尝试下一步，不可走则尝试该点的其他方向
        if () {
            // 继续下一步  
            dfs();  
        }
    }  
}  

non-recursive
procedure DFS-iterative(G,v):
      let S be a stack
      S.push(v)
      while S is not empty
            v ← S.pop()
            if v is not labeled as discovered:
                label v as discovered
                for all edges from v to w in G.adjacentEdges(v) do
                    S.push(w)