216. Combination Sum III(https://leetcode.com/problems/combination-sum-iii/#/description) 이것은 leetcode 216번입니다.자신이 이 문제를 해냈기 때문에 이 문제를 생각했다.이 제목은 비중복 배열 조합이니 비중복 배열 조합부터 말하자.배열 조합에는 두 가지 귀속 방법이 있는데, 중복과 비중복을 구별하고, 아주 작은 코드 변경만 하면 된다.

비반복 배열 조합

방법 1:

사상: 제 index 개 원소에 대해 순서대로 후속 모든 원소 index+i를 보고 그를 조합(시도는 진일보한 귀속을 하는 것이다)

List> re=new ArrayList>();
    public void combine(int index,int k,int n,List temp){
        if(n<0) return;
        if(k==0&&n==0){
            re.add(new ArrayList<>(temp));
            return;
        }
        if(k<=0) return;
        for(int i=index;i<10;i++){
            temp.add(i);
            combine(i+1,k-1, n-i,temp);
            temp.remove(temp.size()-1);
        }
        return;
    }
    public List> combinationSum3(int k, int n) {
        List temp=new ArrayList<>();
        combine(1,k, n, temp);
        return re;
    }

방법 2:

사상: 제 index 개 원소에 대해 이 원소를 넣거나 넣지 않는 두 가지 상황만 보고 다음 원소 index+1로 귀속한다.이 방법은remove 요소가 필요합니다.

List> re=new ArrayList>();
    public void combine(int index,int k,int n,List temp){
        if(n<0) return;
        if(k==0&&n==0){
            re.add(new ArrayList<>(temp));
            return;
        }
        if(index>9) return;
        if(k<=0) return;
        temp.add(index);
        combine(index+1,k-1, n-index,temp);
        temp.remove(temp.size()-1);
        combine(index+1,k, n,temp);
        return;
    }
    public List> combinationSum3(int k, int n) {
        List temp=new ArrayList<>();
        combine(1,k, n, temp);
        return re;
    }

반복 배열 조합 있음

사실 앞의 비중복 배열 조합을 대조하여 중복이 있는 것을 쓰는 것은 이미 매우 간단하다

방법 1:

변경된 곳:combine(i+1,k-1,n-i,temp)가combine(i,k-1,n-i,temp)로 바뀌었습니다. 왜냐하면 i의 원소가 중복 사용될 수 있기 때문입니다.

List> re=new ArrayList>();
    public void combine(int index,int k,int n,List temp){
        if(n<0) return;
        if(k==0&&n==0){
            re.add(new ArrayList<>(temp));
            return;
        }
        if(k<=0) return;
        for(int i=index;i<10;i++){
            temp.add(i);
            combine(i,k-1, n-i,temp);
            temp.remove(temp.size()-1);
        }
        return;
    }
    public List> combinationSum3(int k, int n) {
        List temp=new ArrayList<>();
        combine(1,k, n, temp);
        return re;
    }

방법 2:

변경된 곳:combine(index+1,k-1,n-index,temp)가combine(index,k-1,n-index,temp)로 변한다.인덱스 요소가 중복 사용될 수 있기 때문에

List> re=new ArrayList>();
    public void combine(int index,int k,int n,List temp){
        if(n<0) return;
        if(k==0&&n==0){
            re.add(new ArrayList<>(temp));
            return;
        }
        if(index>9) return;
        if(k<=0) return;
        temp.add(index);
        combine(index,k-1, n-index,temp);
        temp.remove(temp.size()-1);
        combine(index+1,k, n,temp);
        return;
    }
    public List> combinationSum3(int k, int n) {
        List temp=new ArrayList<>();
        combine(1,k, n, temp);
        return re;
    }