Combinations(조합)

1309 단어

문제


Given two integers n and k, return all possible combinations of k numbers out of 1 ... n. Example For example, If n = 4 and k = 2, a solution is: [[2,4],[3,4],[2,3],[1,2],[1,3],[1,4]]

분석


귀속을 이용하여 매번 조작은temp에 하나의 원소만 추가하고 k개의 원소를 추가할 때 결과집중에 추가합니다.두 가지 주의: 1, k개의 원소가 있을 때 반드시temp를 복사해서 결과집에 넣는다. 만약에 직접 넣으면 뒤에 이temp를 계속 조작하면 마지막에 모든 결과가 같다.2,temp가 원소를 삭제할 때를 주의하십시오. 이번에 아래로 귀속될 때 이 원소를 제거해야 합니다.

코드

    /*
     * @param n: Given the range of numbers
     * @param k: Given the numbers of combinations
     * @return: All the combinations of k numbers out of 1..n
     */
    public List> combine(int n, int k) {
        // write your code here
        List> res=new ArrayList();
        LinkedList temp=new LinkedList();
        if(k>0){
            tree(n,res,temp,k,1);
        }
        return res;
    }
    private void tree(int n,List> res,LinkedList temp,int k,int index){
        for(int i=index;i<=n;i++){
            temp.add(i);
            if(temp.size()==k){
                res.add(new ArrayList(temp));
            }else{
                tree(n,res,temp,k,i+1);
            }
            temp.removeLast();
        }
    }
}

좋은 웹페이지 즐겨찾기