class Solution {

    public List<List<Integer>> combine(int n, int k) {

        result = new ArrayList<>();

        List<Integer> ans = new ArrayList<Integer>();

        dfs(ans,n,k,1);

        return result;

    }

    void dfs(List<Integer> ans, int n, int k, int depth){

        if(ans.size()==k) {

            List<Integer> new_ans = new ArrayList<Integer>(ans);

            result.add(new_ans);

            return;

        }

        if(depth>n){

            return;

        }

        ans.add(depth);

        dfs(ans,n,k,depth+1);

        ans.remove(ans.size()-1);

        dfs(ans,n,k,depth+1);

    }

    private List<List<Integer>> result;

}