1. 증가하는 부분 수열

문제 링크: LeetCode

문제 설명: 주어진 배열의 부분 수열 중에서 각 요소가 이전 요소보다 크거나 같은 모든 가능한 부분 수열을 찾아야 합니다. 배열의 원래 순서를 변경할 수 없습니다.

풀이 방법: 이 문제는 조합 문제와 유사하지만, 각 단계에서 현재 요소가 경로(path)의 마지막 요소보다 작으면 건너뜁니다. 또한 배열에 중복 요소가 있을 수 있으므로 중복 제거가 필요합니다. 같은 부모 노드 아래에서 동일한 요소는 건너뛰어야 합니다(부모 노드가 동일하면 같은 요소가 이미 이전에 선택되었기 때문입니다).

중복 제거에는 맵이나 배열을 사용할 수 있습니다. 이 문제에서는 숫자의 범위가 제한되어 있으므로 배열을 사용하는 것이 더 효율적입니다.

class Solution {
private:
    vector 결과;
    vector<int> 경로;

    void 백트래킹(const vector<int>& 숫자들, int 시작인덱스) {
        // 경로 길이가 1보다 크면 결과에 추가
        if (경로.size() > 1)
            결과.push_back(경로);
        // 모든 노드를 수집해야 하므로 return하지 않음
        vector<int> 사용된(201, 0);
        for (int i = 시작인덱스; i < 숫자들.size(); ++i) {
            if ((!경로.empty() && 숫자들[i] < 경로.back()) || 사용된[숫자들[i] + 100] != 0)
                continue;
            사용된[숫자들[i] + 100] = 1;
            경로.push_back(숫자들[i]);
            백트래킹(숫자들, i + 1);
            경로.pop_back();
        }
    }

public:
    vector 증가부분수열찾기(vector<int>& 숫자들) {
        백트래킹(숫자들, 0);
        return 결과;
    }
};

2. 순열

문제 링크: LeetCode

문제 설명: 주어진 숫자 배열의 모든 가능한 순열을 찾아야 합니다. 조합과의 차이점은 선택되지 않은 요소도 계속해서 고려해야 한다는 것입니다.

풀이 방법: 조합과 달리 순열에서는 시작 인덱스가 필요 없습니다. 매번 0부터 시작하지만, 이미 선택된 요소는 건너뛰어야 합니다. 이를 위해 used 배열을 사용하여 선택된 요소를 추적합니다.

class Solution {
private:
    vector 결과;
    vector<int> 현재경로;

    void 백트래킹(const vector<int>& 숫자들, vector<bool> 사용여부){
        if (현재경로.size() == 숫자들.size()){
            결과.push_back(현재경로);
            return;
        }
        for (int i = 0; i < 숫자들.size(); ++i) {
            if (사용여부[i])
                continue;
            사용여부[i] = true;
            현재경로.push_back(숫자들[i]);
            백트래킹(숫자들, 사용여부);
            현재경로.pop_back();
            사용여부[i] = false;
        }
    }

public:
    vector 모든순열(vector<int>& 숫자들) {
        vector<bool> 사용여부(숫자들.size(), false);
        백트래킹(숫자들, 사용여부);
        return 결과;
    }
};

3. 중복 순열

문제 링크: LeetCode

문제 설명: 주어진 배열에 중복 요소가 있을 수 있지만, 결과 집합에는 중복된 순열이 포함되지 않아야 합니다.

풀이 방법: 기본 순열 알고리즘에 중복 제거 로직을 추가합니다. 배열을 먼저 정렬한 후, 이전 요소와 현재 요소가 같고 이전 요소가 아직 사용되지 않은 경우 건너뜁니다.

class Solution {
private:
    vector 최종결과;
    vector<int> 순열경로;

    void 백트래킹(const vector<int>& 숫자들, vector<bool> 사용여부){
        if (순열경로.size() == 숫자들.size()){
            최종결과.push_back(순열경로);
            return;
        }
        for (int i = 0; i < 숫자들.size(); ++i) {
            if (i > 0 && 숫자들[i-1] == 숫자들[i] && 사용여부[i-1] == false)
                continue;
            if (사용여부[i])
                continue;
            사용여부[i] = true;
            순열경로.push_back(숫자들[i]);
            백트래킹(숫자들, 사용여부);
            순열경로.pop_back();
            사용여부[i] = false;
        }
    }

public:
    vector 고유순열(vector<int>& 숫자들) {
        vector<bool> 사용여부(숫자들.size(), false);
        sort(숫자들.begin(), 숫자들.end());
        백트래킹(숫자들, 사용여부);
        return 최종결과;
    }
};